oj.uz

Submission #272415

# Submission time Handle Problem Language Result Execution time Memory
272415 2020-08-18T11:43:23 Z eohomegrownapps Restore Array (RMI19_restore) C++14
100 / 100
 386 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m;
int INF = 1e9;

void relaxedges(){
    int a[20001], b[20001], c[20001];
    for (int i = 0; i<m; i++){
        int l,r,k,v;
        cin>>l>>r>>k>>v;
        r++;
        if (v==0){
            a[i]=l;
            b[i]=r;
            c[i]=k-(r-l);
        } else {
            a[i]=r;
            b[i]=l;
            c[i]=(r-l)-k+1;
        }
    }
    for (int i = 0; i<n; i++){
        a[m+2*i]=i;
        b[m+2*i]=i+1;
        c[m+2*i]=-1;
        a[m+2*i+1]=i+1;
        b[m+2*i+1]=i;
        c[m+2*i+1]=0;
    }
    m+=2*n;
    bool changed = true;
    bool works = true;
    int vals[20001];
    vals[0]=0;
    for (int i = 1; i<=n; i++){
        vals[i]=INF;
    }
    for (int i = 0; i<=n; i++){
        bool changed = false;
        for (int i = 0; i<m; i++){
            if (vals[b[i]]>vals[a[i]]-c[i]){
                vals[b[i]]=vals[a[i]]-c[i];
                changed=true;
            }
        }
        if (changed&&i==n){
            works=false;
        }
        if (!changed){break;}
    }
    if (!works){
        cout<<-1<<'\n';
        return;
    }
    /*for (int i = 0; i<=n; i++){
        cout<<vals[i]<<' ';
    }cout<<'\n';*/
    for (int i = 0; i<n; i++){
        cout<<vals[i+1]-vals[i]<<' ';
    }cout<<'\n';
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>m;
    /*if (n<=18){
        subtask1();
    } else {*/
        relaxedges();
    //}
}

Compilation message

restore.cpp: In function 'void relaxedges()':
restore.cpp:33:10: warning: unused variable 'changed' [-Wunused-variable]
   33 |     bool changed = true;
      |          ^~~~~~~

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 0 ms 384 KB Output is correct
4 Correct 1 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 1 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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 386 ms 640 KB Output is correct
6 Correct 338 ms 640 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 386 ms 640 KB Output is correct
6 Correct 338 ms 640 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 375 ms 640 KB Output is correct
12 Correct 383 ms 648 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 11 ms 640 KB Output is correct
16 Correct 70 ms 640 KB Output is correct

Subtask #4
55.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 0 ms 384 KB Output is correct
4 Correct 1 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 1 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 9 ms 640 KB Output is correct
12 Correct 8 ms 640 KB Output is correct
13 Correct 7 ms 640 KB Output is correct
14 Correct 7 ms 640 KB Output is correct
15 Correct 386 ms 640 KB Output is correct
16 Correct 338 ms 640 KB Output is correct
17 Correct 7 ms 640 KB Output is correct
18 Correct 7 ms 640 KB Output is correct
19 Correct 8 ms 640 KB Output is correct
20 Correct 6 ms 640 KB Output is correct
21 Correct 375 ms 640 KB Output is correct
22 Correct 383 ms 648 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 5 ms 640 KB Output is correct
25 Correct 11 ms 640 KB Output is correct
26 Correct 70 ms 640 KB Output is correct
27 Correct 6 ms 640 KB Output is correct
28 Correct 7 ms 640 KB Output is correct
29 Correct 9 ms 640 KB Output is correct
30 Correct 8 ms 640 KB Output is correct
31 Correct 6 ms 640 KB Output is correct
32 Correct 7 ms 640 KB Output is correct
33 Correct 370 ms 736 KB Output is correct
34 Correct 361 ms 760 KB Output is correct
35 Correct 7 ms 640 KB Output is correct
36 Correct 7 ms 640 KB Output is correct