#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int E = 20020;
int from[E], to[E], cost[E], edges = 0;
int add_edge(int u, int v, int w) {
from[edges] = u;
to[edges] = v;
cost[edges] = w;
return edges++;
}
const int N = 5007;
const int INF = 10001000;
int n, dist[N];
bool ford_bellman() {
dist[0] = 0;
for (int i = 1; i <= n; ++i) {
dist[i] = INF;
}
for (int i = 0; i < n; ++i) {
bool found = false;
for (int e = 0; e < edges; ++e) {
if (dist[from[e]] != INF && dist[from[e]] + cost[e] < dist[to[e]]) {
found = true;
dist[to[e]] = dist[from[e]] + cost[e];
}
}
if (i == n - 1 && found) {
return false;
}
}
return true;
}
int main() {
#ifdef ONPC
freopen("input.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int m;
cin >> n >> m;
while (m--) {
int l, r, k, val;
cin >> l >> r >> k >> val;
--l;
if (val == 0) {
add_edge(l, r, r - l - k);
} else {
add_edge(r, l, -k);
}
}
for (int i = 0; i < n; ++i) {
add_edge(i, i + 1, 1);
add_edge(i + 1, i, 0);
}
if (ford_bellman()) {
for (int i = 1; i <= n; ++i) {
cout << (dist[i] != dist[i - 1]) << " "[i == n];
}
cout << '\n';
} else {
cout << "-1\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
134 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
