oj.uz

Submission #555865

# Submission time Handle Problem Language Result Execution time Memory
555865 2022-05-01T18:10:48 Z mihnea_tudor Restore Array (RMI19_restore) C++17
100 / 100
 593 ms 904 KB 
#include <bits/stdc++.h>

#define NMAX ((int)5e3)
#define INF  ((int)1e9)

using namespace std;

struct edge {
    int dest, cost;
};

int n, m;
vector<edge> a[NMAX + 1];

int dist[NMAX + 1];

bool bellmanford() {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
 
    dist[0] = 0;
 
    for (int cnt = 0; cnt < n; ++cnt) {
        // Check all edges
        for (int node = 0; node <= n; ++node) {
            for (auto it = a[node].begin(); it != a[node].end(); ++it) {
                edge next = *it;
                if (dist[node] + next.cost < dist[next.dest]) {
                    dist[next.dest] = dist[node] + next.cost;
                }
            }
        }
    }
 
    for (int node = 0; node <= n; ++node) {
        for (auto it = a[node].begin(); it != a[node].end(); ++it) {
            edge next = *it;
            if (dist[node] + next.cost < dist[next.dest]) {
                return false;
            }
        }
    }
 
    return true;
}

void add_constraint(int left, int right, int k, int val) {
    if (val == 0) {
        a[left - 1].push_back({right, (right - left + 1) - k});
    } else {
        a[right].push_back({left - 1, -((right - left + 1) - (k - 1))});
    }
}

int main(void) {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int left, right, k, val;
        scanf("%d %d %d %d", &left, &right, &k, &val);

        ++left; ++right;
        add_constraint(left, right, k, val);
    }

    for (int i = 1; i <= n; ++i) {
        a[i - 1].push_back({i, 1});
        a[i].push_back({i - 1, 0});
    }

    if (!bellmanford()) {
        printf("-1\n");
        return 0;
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d ", dist[i] - dist[i - 1]);
    }

    printf("\n");

    return 0;
}

Compilation message

restore.cpp: In function 'int main()':
restore.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
restore.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d %d %d %d", &left, &right, &k, &val);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 712 KB Output is correct
2 Correct 272 ms 704 KB Output is correct
3 Correct 263 ms 712 KB Output is correct
4 Correct 260 ms 724 KB Output is correct
5 Correct 500 ms 732 KB Output is correct
6 Correct 502 ms 844 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 712 KB Output is correct
2 Correct 272 ms 704 KB Output is correct
3 Correct 263 ms 712 KB Output is correct
4 Correct 260 ms 724 KB Output is correct
5 Correct 500 ms 732 KB Output is correct
6 Correct 502 ms 844 KB Output is correct
7 Correct 299 ms 744 KB Output is correct
8 Correct 292 ms 736 KB Output is correct
9 Correct 296 ms 740 KB Output is correct
10 Correct 289 ms 740 KB Output is correct
11 Correct 581 ms 736 KB Output is correct
12 Correct 593 ms 876 KB Output is correct
13 Correct 286 ms 884 KB Output is correct
14 Correct 314 ms 884 KB Output is correct
15 Correct 295 ms 892 KB Output is correct
16 Correct 292 ms 884 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 266 ms 712 KB Output is correct
12 Correct 272 ms 704 KB Output is correct
13 Correct 263 ms 712 KB Output is correct
14 Correct 260 ms 724 KB Output is correct
15 Correct 500 ms 732 KB Output is correct
16 Correct 502 ms 844 KB Output is correct
17 Correct 299 ms 744 KB Output is correct
18 Correct 292 ms 736 KB Output is correct
19 Correct 296 ms 740 KB Output is correct
20 Correct 289 ms 740 KB Output is correct
21 Correct 581 ms 736 KB Output is correct
22 Correct 593 ms 876 KB Output is correct
23 Correct 286 ms 884 KB Output is correct
24 Correct 314 ms 884 KB Output is correct
25 Correct 295 ms 892 KB Output is correct
26 Correct 292 ms 884 KB Output is correct
27 Correct 287 ms 876 KB Output is correct
28 Correct 288 ms 888 KB Output is correct
29 Correct 279 ms 884 KB Output is correct
30 Correct 292 ms 888 KB Output is correct
31 Correct 310 ms 884 KB Output is correct
32 Correct 284 ms 876 KB Output is correct
33 Correct 591 ms 892 KB Output is correct
34 Correct 552 ms 904 KB Output is correct
35 Correct 289 ms 880 KB Output is correct
36 Correct 292 ms 884 KB Output is correct