oj.uz

Submission #203450

# Submission time Handle Problem Language Result Execution time Memory
203450 2020-02-20T17:44:09 Z alexandra_udristoiu Restore Array (RMI19_restore) C++14
0 / 100
 37 ms 1144 KB 
#include<iostream>
#include<queue>
#include<vector>
#define f first
#define s second
using namespace std;
int n, m, i, x, y, t, val, nod, vecin;
int num[5005], sol[5005], viz[5005], sum[5005];
pair<int, int> d[5005];
queue<int> c;
struct str{
    int x, minim, maxim;
};
vector<str> v[5005];
int verif(int x){
    if(sum[x] < d[x].f || sum[x] > d[x].s){
        return 0;
    }
    for(int i = 0; i < v[x].size(); i++){
        int y = v[x][i].x;
        if(sum[x] - sum[y] < v[x][i].minim || sum[x] - sum[y] > v[x][i].maxim){
            return 0;
        }
    }
    return 1;
}
int main(){
    cin>> n >> m;
    for(i = 1; i <= m; i++){
        cin>> x >> y >> val >> t;
        y++;
        if(t == 1){
            v[x].push_back( {y, 0, val - 1} );
            v[y].push_back( {x, 0, val - 1} );
        }
        else{
            v[x].push_back( {y, val, y - x + 1} );
            v[y].push_back( {x, val, y - x + 1} );
        }
    }
    for(i = 1; i <= n; i++){
        v[i].push_back( {i - 1, 0, 1} );
        v[i - 1].push_back( {i, 0, 1} );
    }
    for(i = 1; i <= n; i++){
        d[i] = make_pair(0, i);
        num[i] = i;
    }
    viz[0] = 1;
    c.push(0);
    while(!c.empty()){
        nod = c.front();
        viz[nod] = 0;
        c.pop();
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i].x;
            if(vecin > nod){
                d[vecin].f = max(d[vecin].f, d[nod].f + v[nod][i].minim);
                d[vecin].s = min(d[vecin].s, d[nod].s + v[nod][i].maxim);
            }
            else{
                d[vecin].f = max(d[vecin].f, d[nod].f - v[nod][i].maxim);
                d[vecin].s = min(d[vecin].s, d[nod].s - v[nod][i].minim);
            }
            if(d[vecin].s - d[vecin].f < num[vecin]){
                num[vecin] = d[vecin].s - d[vecin].f;
                if(viz[vecin] == 0){
                    viz[vecin] = 1;
                    c.push(vecin);
                }
            }
            if(d[vecin].s < d[vecin].f){
                cout<< -1;
                return 0;
            }
        }
    }
    for(i = 1; i <= n; i++){
        sum[i] = sum[i - 1];
        if(verif(i)){
            sol[i] = 1;
        }
        else{
            sol[i] = 0;
            sum[i]++;
        }
    }
    for(i = 1; i <= n; i++){
        cout<< sol[i] <<" ";
    }
}

Compilation message

restore.cpp: In function 'int verif(int)':
restore.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[x].size(); i++){
                    ~~^~~~~~~~~~~~~
restore.cpp: In function 'int main()':
restore.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 1144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -