oj.uz

답안 #203447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203447 2020-02-20T17:19:24 Z alexandra_udristoiu Restore Array (RMI19_restore) C++14
0 / 100
 33 ms 1272 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, sum;
int num[5005], sol[5005], viz[5005];
pair<int, int> d[5005];
queue<int> c;
struct str{
    int x, minim, maxim;
};
vector<str> v[5005];
int main(){
    cin>> n >> m;
    for(i = 1; i <= m; i++){
        cin>> x >> y >> val >> t;
        x--;
        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);
                }
            }
        }
    }
    for(i = 1; i <= n; i++){
        if(d[i].f <= sum){
            sol[i] = 0;
        }
        else{
            sol[i] = 1;
            sum++;
        }
    }
    for(i = 1; i <= n; i++){
        cout<< sol[i] <<" ";
    }
}

Compilation message

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -