Submission #203453

#	Time	Username	Problem	Language	Result	Execution time	Memory
203453		alexandra_udristoiu	Restore Array (RMI19_restore)	C++14	7 / 100	40 ms	1272 KiB

restore

#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(y > x){
            continue;
        }
        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 (stderr)

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:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55