#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#ifdef LOCAL
ifstream fin("restore.in");
ofstream fout("restore.out");
#else
#define fin cin
#define fout cout
#endif
const int NMAX = 5000;
const int INF = 1e9;
int n, m;
vector<pair<int, int>> adj[NMAX + 1];
int dist[NMAX + 1], freq[NMAX + 1];
bool inQ[NMAX + 1];
bool bell(int u) {
fill(dist, dist + n + 1, INF);
fill(inQ, inQ + n + 1, 0);
queue<int> q;
q.push(u);
dist[u] = 0;
inQ[u] = 1;
while(!q.empty()) {
int v = q.front();
q.pop();
inQ[v] = 0;
for(const auto it: adj[v]) {
if(dist[it.first] > dist[v] + it.second) {
dist[it.first] = dist[v] + it.second;
if(!inQ[it.first]) {
q.push(it.first);
inQ[it.first] = 1;
}
if(++freq[it.first] > n || dist[it.first] < 0) {
return 0;
}
}
}
}
return 1;
}
int main() {
ios_base :: sync_with_stdio(0); fin.tie(nullptr);
fin >> n >> m;
for(int i = 1; i <= m; i++) {
int l, r, k, value;
fin >> l >> r >> k >> value;
l++; r++;
if(value == 0) {
adj[l - 1].push_back({r, r - l + 1 - k});
} else {
adj[r].push_back({l - 1, -(r - l + 1) + k - 1});
}
}
for(int i = 1; i <= n; i++) {
adj[i - 1].push_back({i, 1});
adj[i].push_back({i - 1, -0});
}
if(bell(0)) {
for(int i = 1; i <= n; i++) {
fout << dist[i] - dist[i - 1] << " ";
}
fout << '\n';
} else {
fout << "-1\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
724 KB |
Output is correct |
2 |
Correct |
11 ms |
784 KB |
Output is correct |
3 |
Correct |
12 ms |
772 KB |
Output is correct |
4 |
Correct |
10 ms |
724 KB |
Output is correct |
5 |
Correct |
4 ms |
724 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
724 KB |
Output is correct |
2 |
Correct |
11 ms |
784 KB |
Output is correct |
3 |
Correct |
12 ms |
772 KB |
Output is correct |
4 |
Correct |
10 ms |
724 KB |
Output is correct |
5 |
Correct |
4 ms |
724 KB |
Output is correct |
6 |
Correct |
4 ms |
852 KB |
Output is correct |
7 |
Correct |
12 ms |
956 KB |
Output is correct |
8 |
Correct |
12 ms |
968 KB |
Output is correct |
9 |
Correct |
17 ms |
980 KB |
Output is correct |
10 |
Correct |
10 ms |
852 KB |
Output is correct |
11 |
Correct |
4 ms |
852 KB |
Output is correct |
12 |
Correct |
4 ms |
852 KB |
Output is correct |
13 |
Correct |
11 ms |
960 KB |
Output is correct |
14 |
Correct |
19 ms |
980 KB |
Output is correct |
15 |
Correct |
30 ms |
964 KB |
Output is correct |
16 |
Correct |
115 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 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 |
10 ms |
724 KB |
Output is correct |
12 |
Correct |
11 ms |
784 KB |
Output is correct |
13 |
Correct |
12 ms |
772 KB |
Output is correct |
14 |
Correct |
10 ms |
724 KB |
Output is correct |
15 |
Correct |
4 ms |
724 KB |
Output is correct |
16 |
Correct |
4 ms |
852 KB |
Output is correct |
17 |
Correct |
12 ms |
956 KB |
Output is correct |
18 |
Correct |
12 ms |
968 KB |
Output is correct |
19 |
Correct |
17 ms |
980 KB |
Output is correct |
20 |
Correct |
10 ms |
852 KB |
Output is correct |
21 |
Correct |
4 ms |
852 KB |
Output is correct |
22 |
Correct |
4 ms |
852 KB |
Output is correct |
23 |
Correct |
11 ms |
960 KB |
Output is correct |
24 |
Correct |
19 ms |
980 KB |
Output is correct |
25 |
Correct |
30 ms |
964 KB |
Output is correct |
26 |
Correct |
115 ms |
972 KB |
Output is correct |
27 |
Correct |
6 ms |
852 KB |
Output is correct |
28 |
Correct |
5 ms |
976 KB |
Output is correct |
29 |
Correct |
6 ms |
852 KB |
Output is correct |
30 |
Correct |
6 ms |
996 KB |
Output is correct |
31 |
Correct |
7 ms |
840 KB |
Output is correct |
32 |
Correct |
7 ms |
980 KB |
Output is correct |
33 |
Correct |
4 ms |
852 KB |
Output is correct |
34 |
Correct |
5 ms |
844 KB |
Output is correct |
35 |
Correct |
9 ms |
980 KB |
Output is correct |
36 |
Correct |
6 ms |
980 KB |
Output is correct |