oj.uz

Submission #333316

# Submission time Handle Problem Language Result Execution time Memory
333316 2020-12-05T12:13:46 Z keko37 Restore Array (RMI19_restore) C++14
20 / 100
 600 ms 1260 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 5005;

int n, m;
int dist[MAXN];
vector <pi> v[MAXN];

bool relax () {
    bool ok = 0;
    for (int i = 0; i <= n + 1; i++) {
        for (auto pp : v[i]) {
            int sus = pp.first, w = pp.second;
            if (dist[sus] > dist[i] + w) {
                dist[sus] = dist[i] + w;
                ok = 1;
            }
        }
    }
    return ok;
}

void bellman_ford () {
    dist[n + 1] = 0;
    for (int i = 0; i <= n; i++) dist[i] = 1e9;
    for (int i = 0; i < n + 1; i++) {
        relax();
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        v[i - 1].push_back({i, 1});
        v[i].push_back({i - 1, 0});
    }
    for (int i = 0; i < m; i++) {
        int lef, rig, k, val;
        cin >> lef >> rig >> k >> val;
        lef++; rig++;
        if (val == 0) {
            v[lef - 1].push_back({rig, rig - lef + 1 - k});
        } else {
            v[rig].push_back({lef - 1, k-1 - (rig - lef + 1)});
        }
    }
    for (int i = 0; i <= n; i++) {
        v[n + 1].push_back({i, 0});
    }
    bellman_ford();
    if (relax()) {
        cout << -1;
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        cout << dist[i] - dist[i - 1] << " ";
    }
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 1004 KB Output is correct
2 Correct 352 ms 1132 KB Output is correct
3 Correct 349 ms 1132 KB Output is correct
4 Correct 355 ms 1152 KB Output is correct
5 Correct 515 ms 1004 KB Output is correct
6 Correct 523 ms 1004 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 1004 KB Output is correct
2 Correct 352 ms 1132 KB Output is correct
3 Correct 349 ms 1132 KB Output is correct
4 Correct 355 ms 1152 KB Output is correct
5 Correct 515 ms 1004 KB Output is correct
6 Correct 523 ms 1004 KB Output is correct
7 Correct 401 ms 1260 KB Output is correct
8 Correct 391 ms 1132 KB Output is correct
9 Correct 385 ms 1260 KB Output is correct
10 Correct 393 ms 1260 KB Output is correct
11 Execution timed out 645 ms 1004 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 358 ms 1004 KB Output is correct
12 Correct 352 ms 1132 KB Output is correct
13 Correct 349 ms 1132 KB Output is correct
14 Correct 355 ms 1152 KB Output is correct
15 Correct 515 ms 1004 KB Output is correct
16 Correct 523 ms 1004 KB Output is correct
17 Correct 401 ms 1260 KB Output is correct
18 Correct 391 ms 1132 KB Output is correct
19 Correct 385 ms 1260 KB Output is correct
20 Correct 393 ms 1260 KB Output is correct
21 Execution timed out 645 ms 1004 KB Time limit exceeded
22 Halted 0 ms 0 KB -