oj.uz

Submission #272870

# Submission time Handle Problem Language Result Execution time Memory
272870 2020-08-18T17:26:53 Z Atill83 Restore Array (RMI19_restore) C++14
7 / 100
 600 ms 960 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;
vector<pair<int, pii>> ed;
ll d[MAXN];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;

    for(int i = 0; i <= n; i++) d[i] = mod;
    for(int i = 0; i < m; i++){
        int l, r, k, val;
        cin>>l>>r>>k>>val;
        l++;r++;
        if(val == 0){
            ed.push_back({-k, {r, l - 1}});
        }else{
            ed.push_back({k - 1, {l - 1, r}});
        }
    }

    for(int i = 0; i < n; i++){
        ed.push_back({0, {i + 1, i}});
        ed.push_back({1, {i, i + 1}});
    }
    d[0] = 0;
    bool done;
    for(int i = 0; i <= n; i++){

        done = 0;

        for(auto j: ed){
            if(d[j.ss.ff] < mod){
                if(d[j.ss.ss] > d[j.ss.ff] + j.ff){
                    done = 1;
                    d[j.ss.ss] = d[j.ss.ff] + j.ff;
                }
            }
        }
    }

    if(done){
        cout<<-1<<endl;
        return 0;
    }

    for(int i = 0; i < n; i++){
        cout<<((d[i + 1] - d[i]) ^ 1)<<" ";

    }


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

restore.cpp: In function 'int main()':
restore.cpp:60:5: warning: 'done' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     if(done){
      |     ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 960 KB Output is correct
2 Correct 148 ms 960 KB Output is correct
3 Correct 154 ms 960 KB Output is correct
4 Correct 151 ms 960 KB Output is correct
5 Execution timed out 632 ms 960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 960 KB Output is correct
2 Correct 148 ms 960 KB Output is correct
3 Correct 154 ms 960 KB Output is correct
4 Correct 151 ms 960 KB Output is correct
5 Execution timed out 632 ms 960 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 148 ms 960 KB Output is correct
12 Correct 148 ms 960 KB Output is correct
13 Correct 154 ms 960 KB Output is correct
14 Correct 151 ms 960 KB Output is correct
15 Execution timed out 632 ms 960 KB Time limit exceeded
16 Halted 0 ms 0 KB -