# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
198591 | 2020-01-26T18:00:38 Z | Akashi | Restore Array (RMI19_restore) | C++14 | 299 ms | 696 KB |
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; int n, m; struct edge{ int x, y, c; }; vector <edge> v; void add_edge(int x, int y, int c){ v.push_back({x, y, c}); } int d[5005]; queue <int> q; bool bellman(){ for(int i = 1; i <= n ; ++i) d[i] = INF; d[0] = 0; for(int i = 1; i <= n + 1 ; ++i) for(auto it : v) d[it.y] = min(d[it.y], d[it.x] + it.c); for(auto it : v) if(d[it.y] > d[it.x] + it.c) return 0; return 1; } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n ; ++i) add_edge(i - 1, i, 1); int l, r, k, val; for(int i = 1; i <= m ; ++i){ scanf("%d%d%d%d", &l, &r, &k, &val); ++l; ++r; if(val == 1) add_edge(r, l - 1, (k - 1) - (r - l + 1)); else add_edge(l - 1, r, (r - l + 1) - k); } bool ok = bellman(); if(!ok) printf("-1"); else{ for(int i = 1; i <= n ; ++i) printf("%d ", d[i] - d[i - 1]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Incorrect | 5 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 286 ms | 696 KB | Output is correct |
2 | Correct | 287 ms | 696 KB | Output is correct |
3 | Correct | 287 ms | 696 KB | Output is correct |
4 | Correct | 289 ms | 696 KB | Output is correct |
5 | Correct | 287 ms | 632 KB | Output is correct |
6 | Correct | 288 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 286 ms | 696 KB | Output is correct |
2 | Correct | 287 ms | 696 KB | Output is correct |
3 | Correct | 287 ms | 696 KB | Output is correct |
4 | Correct | 289 ms | 696 KB | Output is correct |
5 | Correct | 287 ms | 632 KB | Output is correct |
6 | Correct | 288 ms | 632 KB | Output is correct |
7 | Correct | 294 ms | 696 KB | Output is correct |
8 | Correct | 297 ms | 696 KB | Output is correct |
9 | Incorrect | 299 ms | 696 KB | Integer -15 violates the range [-1, 1] |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Incorrect | 5 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |