#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int n, m, target, l,r;
vector<int> edges[N];
vector<bool> used;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N;
m = X.size();
for(int i=0;i<m;i++){
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
int Q = S.size();
vector<int> ans;
for(int i=0;i<Q;i++){
l = L[i], r = R[i];
if(S[i] < l)ans.push_back(0);
else {
used.assign(n,false);
queue<tuple<int,int,int>> q; // {form, u, isch};
q.push({0, S[i], (S[i]>=l&&S[i]<=r)?1:0});
used[S[i]] = true;
int ok = 0;
while(!q.empty()){
int f, u, is;
tie(f, u, is) = q.front();q.pop();
// cout << u << ' ' << f << ' ' << is << '\n';
if(u == E[i] && (f || is)){
ok = 1;
break;
}
for(auto v : edges[u]){
if(used[v] || (f && v>r) || (!is && !f && v<l))continue;
used[v] = true;
if(v < l)q.push({1, v, 0});
else if(f)q.push({f, v, 0});
else q.push({0, v, (v>=l&&v<=r)|is});
}
}//cout << '\n';
ans.push_back(ok);
}
}return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
217 ms |
19708 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
