Submission #442026

#	Time	Username	Problem	Language	Result	Execution time	Memory
442026		JovanB	Restore Array (RMI19_restore)	C++17	7 / 100	634 ms	908 KiB

restore

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int MAXN = 5000;

int dist[MAXN+5];

const int INF = 1000000;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    vector <tuple <int, int, int>> edges;
    for(int i=1; i<=m; i++){
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++;
        r++;
        if(val == 1) edges.push_back({l-1, r, k-1});
        else edges.push_back({r, l-1, -k});
    }
    for(int i=1; i<=n; i++){
        edges.push_back({i-1, i, 1});
        edges.push_back({i, i-1, 0});
    }
    for(int i=1; i<=n; i++) dist[i] = INF;
    for(int k=0; k<n; k++){
        for(auto x : edges){
            int a = get<0>(x);
            int b = get<1>(x);
            int c = get<2>(x);
            if(dist[a] != INF && dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    for(auto x : edges){
        int a = get<0>(x);
            int b = get<1>(x);
            int c = get<2>(x);
            if(dist[a] != INF && dist[b] > dist[a] + c){
                cout << "-1\n";
                return 0;
            }
    }
    for(int i=1; i<=n; i++){
        if(dist[i] != dist[i-1]) cout << "0 ";
        else cout << "1 ";
    }
    cout << "\n";
    return 0;
}

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