#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<pair<long long , long long> >gr[2000000];
long long dist[2000000] , vis[2000000];
priority_queue<pair<long long , long long> >q;
vector<vector<long long> >edge;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long menge , numm , nummer , que , cmp , bi;
cin >> menge >> que;
for(long long i = 0 ; i < menge; i++){
gr[i].push_back({i + 1 , 1});
gr[i + 1].push_back({i , 0});
edge.push_back({i , i + 1 , 1});
edge.push_back({i + 1, i , 0});
}
while(que--){
cin >> numm >> nummer >> cmp >> bi;
// numm++;
nummer++;
if(bi == 0){
cmp = nummer - numm - cmp;
gr[numm].push_back({nummer , cmp});
edge.push_back({numm , nummer , cmp});
}
else{
cmp = nummer - numm - cmp + 1;
cmp *= -1;
gr[nummer].push_back({numm , cmp});
edge.push_back({nummer , numm , cmp});
}
}
for(long long i = 0 ; i < 2000000 ; i++){
dist[i] = inf;
}
dist[0] = 0;
for(long long k = 0 ; k < menge ; k++){
for(long long i = 0 ; i < edge.size() ; i++){
if(dist[edge[i][0]] != inf && dist[edge[i][0]] + edge[i][2] < dist[edge[i][1]]){
dist[edge[i][1]] = dist[edge[i][0]] + edge[i][2];
}
}
}
for(long long i = 0 ; i < edge.size() ; i++){
if(dist[edge[i][0]] != inf && dist[edge[i][0]] + edge[i][2] < dist[edge[i][1]]){
cout << -1 << "\n";
return 0;
}
}
for(long long i = 0 ; i < menge ; i++){
// cout << dist[i] << "\n";
if(dist[i] == dist[i + 1]){
cout << 0 << ' ';
}
else{
cout << 1 << ' ';
}
}
}
Compilation message
restore.cpp: In function 'int main()':
restore.cpp:44:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(long long i = 0 ; i < edge.size() ; i++){
| ~~^~~~~~~~~~~~~
restore.cpp:50:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(long long i = 0 ; i < edge.size() ; i++){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
62848 KB |
Output is correct |
2 |
Correct |
29 ms |
62932 KB |
Output is correct |
3 |
Correct |
30 ms |
62968 KB |
Output is correct |
4 |
Correct |
29 ms |
62944 KB |
Output is correct |
5 |
Correct |
29 ms |
62884 KB |
Output is correct |
6 |
Correct |
34 ms |
62860 KB |
Output is correct |
7 |
Correct |
30 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
62932 KB |
Output is correct |
9 |
Correct |
29 ms |
62916 KB |
Output is correct |
10 |
Correct |
30 ms |
62832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
258 ms |
64508 KB |
Output is correct |
2 |
Correct |
260 ms |
64552 KB |
Output is correct |
3 |
Correct |
249 ms |
64524 KB |
Output is correct |
4 |
Correct |
226 ms |
64556 KB |
Output is correct |
5 |
Correct |
586 ms |
64516 KB |
Output is correct |
6 |
Correct |
595 ms |
64576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
258 ms |
64508 KB |
Output is correct |
2 |
Correct |
260 ms |
64552 KB |
Output is correct |
3 |
Correct |
249 ms |
64524 KB |
Output is correct |
4 |
Correct |
226 ms |
64556 KB |
Output is correct |
5 |
Correct |
586 ms |
64516 KB |
Output is correct |
6 |
Correct |
595 ms |
64576 KB |
Output is correct |
7 |
Correct |
266 ms |
64772 KB |
Output is correct |
8 |
Correct |
268 ms |
64748 KB |
Output is correct |
9 |
Correct |
265 ms |
64740 KB |
Output is correct |
10 |
Correct |
258 ms |
64688 KB |
Output is correct |
11 |
Correct |
579 ms |
64632 KB |
Output is correct |
12 |
Correct |
580 ms |
64636 KB |
Output is correct |
13 |
Correct |
231 ms |
64672 KB |
Output is correct |
14 |
Correct |
233 ms |
64668 KB |
Output is correct |
15 |
Correct |
250 ms |
64756 KB |
Output is correct |
16 |
Correct |
262 ms |
64752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
62848 KB |
Output is correct |
2 |
Correct |
29 ms |
62932 KB |
Output is correct |
3 |
Correct |
30 ms |
62968 KB |
Output is correct |
4 |
Correct |
29 ms |
62944 KB |
Output is correct |
5 |
Correct |
29 ms |
62884 KB |
Output is correct |
6 |
Correct |
34 ms |
62860 KB |
Output is correct |
7 |
Correct |
30 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
62932 KB |
Output is correct |
9 |
Correct |
29 ms |
62916 KB |
Output is correct |
10 |
Correct |
30 ms |
62832 KB |
Output is correct |
11 |
Correct |
258 ms |
64508 KB |
Output is correct |
12 |
Correct |
260 ms |
64552 KB |
Output is correct |
13 |
Correct |
249 ms |
64524 KB |
Output is correct |
14 |
Correct |
226 ms |
64556 KB |
Output is correct |
15 |
Correct |
586 ms |
64516 KB |
Output is correct |
16 |
Correct |
595 ms |
64576 KB |
Output is correct |
17 |
Correct |
266 ms |
64772 KB |
Output is correct |
18 |
Correct |
268 ms |
64748 KB |
Output is correct |
19 |
Correct |
265 ms |
64740 KB |
Output is correct |
20 |
Correct |
258 ms |
64688 KB |
Output is correct |
21 |
Correct |
579 ms |
64632 KB |
Output is correct |
22 |
Correct |
580 ms |
64636 KB |
Output is correct |
23 |
Correct |
231 ms |
64672 KB |
Output is correct |
24 |
Correct |
233 ms |
64668 KB |
Output is correct |
25 |
Correct |
250 ms |
64756 KB |
Output is correct |
26 |
Correct |
262 ms |
64752 KB |
Output is correct |
27 |
Correct |
229 ms |
64652 KB |
Output is correct |
28 |
Correct |
273 ms |
64724 KB |
Output is correct |
29 |
Correct |
273 ms |
64772 KB |
Output is correct |
30 |
Correct |
236 ms |
64756 KB |
Output is correct |
31 |
Correct |
265 ms |
64652 KB |
Output is correct |
32 |
Correct |
230 ms |
64696 KB |
Output is correct |
33 |
Execution timed out |
605 ms |
64720 KB |
Time limit exceeded |
34 |
Halted |
0 ms |
0 KB |
- |