oj.uz

Submission #555863

# Submission time Handle Problem Language Result Execution time Memory
555863 2022-05-01T18:04:59 Z mihnea_tudor Restore Array (RMI19_restore) C++14
20 / 100
 600 ms 924 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];
int pred[NMAX + 1];
bool in_queue[NMAX + 1];
int cnt_in_queue[NMAX + 1];

bool bellmanford() {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        pred[i] = -1;
    }
 
    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;
                    pred[next.dest] = node;
                }
            }
        }
    }
 
    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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
restore.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         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 1 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 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 280 ms 732 KB Output is correct
2 Correct 293 ms 856 KB Output is correct
3 Correct 272 ms 724 KB Output is correct
4 Correct 279 ms 736 KB Output is correct
5 Correct 563 ms 756 KB Output is correct
6 Correct 540 ms 852 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 732 KB Output is correct
2 Correct 293 ms 856 KB Output is correct
3 Correct 272 ms 724 KB Output is correct
4 Correct 279 ms 736 KB Output is correct
5 Correct 563 ms 756 KB Output is correct
6 Correct 540 ms 852 KB Output is correct
7 Correct 299 ms 908 KB Output is correct
8 Correct 319 ms 924 KB Output is correct
9 Correct 301 ms 912 KB Output is correct
10 Correct 283 ms 820 KB Output is correct
11 Execution timed out 636 ms 908 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 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 280 ms 732 KB Output is correct
12 Correct 293 ms 856 KB Output is correct
13 Correct 272 ms 724 KB Output is correct
14 Correct 279 ms 736 KB Output is correct
15 Correct 563 ms 756 KB Output is correct
16 Correct 540 ms 852 KB Output is correct
17 Correct 299 ms 908 KB Output is correct
18 Correct 319 ms 924 KB Output is correct
19 Correct 301 ms 912 KB Output is correct
20 Correct 283 ms 820 KB Output is correct
21 Execution timed out 636 ms 908 KB Time limit exceeded
22 Halted 0 ms 0 KB -