oj.uz

Submission #412269

# Submission time Handle Problem Language Result Execution time Memory
412269 2021-05-26T16:24:40 Z fvogel499 Restore Array (RMI19_restore) C++14
0 / 100
 600 ms 1092 KB 
/*
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.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 1092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 1092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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