Submission #412269

#	Time	Username	Problem	Language	Result	Execution time	Memory
412269		fvogel499	Restore Array (RMI19_restore)	C++14	0 / 100	1088 ms	1092 KiB

restore

/*
File created on 05/26/2021 at 16:37:53.
Link to problem: https://oj.uz/problem/view/RMI19_restore
Description: sp in negative graph
Time complexity: O(N(N+M))
Space complexity: O(N^2+M)
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

#define ll long long

const int inf = 1e9;

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    int n, nbReq;
    cin >> n >> nbReq;

    map<pii, int> edges;
    for (int i = 0; i < n; i++) {
        edges[pii(i+1, i)] = 0;
    }

    for (int i = 0; i < nbReq; i++) {
        int l, r, k, v;
        cin >> l >> r >> k >> v;
        l++;
        r++;
        if (v == 0) {
            int assign = (r-l+1)-k;
            if (edges.find(pii(r, l-1)) == edges.end()) edges[pii(r, l-1)] = assign;
            else edges[pii(r, l-1)] = min(edges[pii(r, l-1)], assign);
        }
        else {
            int assign = -k;
            if (edges.find(pii(l-1, r)) == edges.end()) edges[pii(l-1, r)] = assign;
            else edges[pii(l-1, r)] = min(edges[pii(l-1, r)], assign);
        }
    }

    int dist [n+1];
    for (int i = 0; i < n; i++) dist[i] = inf;

    dist[n-1] = 0;

    // for (auto e : edges) cout << e.f.f << " " << e.f.s << " " << e.s << endl;

    for (int _ = 0; _ < n+1; _++) {
        for (auto e : edges) {
            dist[e.f.s] = min(dist[e.f.s], dist[e.f.f]+-e.s);
        }
    }

    for (int i = 0; i < n; i++) {
        if (dist[i+1]-dist[i] == 0) {
            cout << 0;
        }
        else {
            cout << 1;
        }
        cout << " ";
    }

    int d = 0;
    d++;
}

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