oj.uz

Submission #853470

# Submission time Handle Problem Language Result Execution time Memory
853470 2023-09-24T12:00:10 Z lolismek Restore Array (RMI19_restore) C++14
0 / 100
 7 ms 812 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

#define pii pair <int, int>

using namespace std;

const int NMAX = 5000;
const int INF = 1e9 + 1;

vector <pii> adj[NMAX + 1];

int d[NMAX + 1];

bool inq[NMAX + 1];
int f[NMAX + 1];

int ans[NMAX + 1];

int main(){

    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= m; i++){
        int l, r, k, v;
        cin >> l >> r >> k >> v;
        ++l, ++r;

        if(v == 1){
            adj[l - 1].push_back({r, k - 1});
        }else{
            adj[r].push_back({l - 1, -k});
        }
    }

    for(int i = 0; i <= n; i++){
        d[i] = INF;
    }

    queue <int> Q;
    Q.push(0);
    d[0] = 0;
    inq[0] = true;

    while(!Q.empty()){
        int node = Q.front();
        Q.pop();

        inq[node] = false;

        if(++f[node] > n){
            cout << -1 << '\n';
            exit(0);
        }

        for(pii vec : adj[node]){
            if(d[node] + vec.second < d[vec.first]){
                d[vec.first] = d[node] + vec.second;
                if(!inq[vec.first]){
                    Q.push(vec.first);
                }
            }
        }
    }

    vector <pii> aux;
    for(int i = 1; i <= n; i++){
        if(d[i] != INF){
            aux.push_back({i, d[i]});
        }
    }

    sort(aux.begin(), aux.end());



    for(int i = (int)aux.size() - 1; i >= 0; i--){
        int r = aux[i].second;
        int sz = aux[i].first;
        if(i > 0){
            r -= aux[i - 1].second;
            sz -= aux[i - 1].first;
        }

        if(r > sz){
            cout << -1 << '\n';
            exit(0);
        }

        for(int j = aux[i].first; r > 0; j--, r--){
            ans[j] = 1;
        }
    }

    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }
    cout << '\n';
   

    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 13.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 55.0

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