제출 #853470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853470		lolismek	Restore Array (RMI19_restore)	C++14	0 / 100	7 ms	812 KiB

restore

#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
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55