#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
struct city {
vi con;
bool visited_normal=false;
bool visited_werewolf=false;
};
vector<city> cities;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
int Q = S.size();
int M = X.size();
cities.resize(N);
for(int m=0; m<M; m++) {
cities[X[m]].con.push_back(Y[m]);
cities[Y[m]].con.push_back(X[m]);
}
vi A(Q,0);
for (int i = 0; i < Q; ++i) {
/*if(S[i]<L[i] or E[i]>R[i]) { //impossible
//A[i] = 0;
continue;
}*/
queue<pair<int,bool>> bfs;
bfs.push({S[i],false});
while(!bfs.empty()) {
int c;
bool ww;
tie(c,ww)=bfs.front();
bfs.pop();
if(c==E[i]) {
A[i]=1;
break;
}
if(ww and cities[c].visited_werewolf) continue;
if(!ww and cities[c].visited_normal) continue;
bool transform=false;
if(!ww and c<=R[i] and !cities[c].visited_werewolf) transform=true;
if(!ww) cities[c].visited_normal=true;
if(ww or transform) cities[c].visited_werewolf=true;
for(int other:cities[c].con) {
if(!ww and other>=L[i] and !cities[other].visited_normal) bfs.push({other,false});
if((ww or transform) and other<=R[i] and !cities[other].visited_werewolf) bfs.push({other,true});
}
}
for(int n=0; n<N; n++) cities[n].visited_normal=cities[n].visited_werewolf=false;
//A[i] = 0;
}
return A;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
221 ms |
768 KB |
Output is correct |
11 |
Correct |
156 ms |
888 KB |
Output is correct |
12 |
Correct |
25 ms |
768 KB |
Output is correct |
13 |
Correct |
188 ms |
828 KB |
Output is correct |
14 |
Correct |
146 ms |
888 KB |
Output is correct |
15 |
Correct |
313 ms |
940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4032 ms |
31480 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
221 ms |
768 KB |
Output is correct |
11 |
Correct |
156 ms |
888 KB |
Output is correct |
12 |
Correct |
25 ms |
768 KB |
Output is correct |
13 |
Correct |
188 ms |
828 KB |
Output is correct |
14 |
Correct |
146 ms |
888 KB |
Output is correct |
15 |
Correct |
313 ms |
940 KB |
Output is correct |
16 |
Execution timed out |
4032 ms |
31480 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |