#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int Nx = 200000;
vector<int> gr[Nx+5];
/*
struct node{
int x;
bool form; // 0 human 1 werewolf
node(){}
node(int _x,bool _form){
x = _x;
form = _form;
}
};*/
int e,l,r;
bool vis[Nx+5][3];
bool pre[Nx+5][3];
bool dfs(int node,bool form){
if(node == e && form){
return 1;
}
if(form && node > r)return 0;
if(!form && node < l)return 0;
bool &ans = pre[node][form];
if(vis[node][form])return ans;
vis[node][form] = 1;
for(auto u:gr[node]){
if(form && u <= r){
ans = ans || dfs(u,1);
}else if(!form){
if(u >= l)ans = ans || dfs(u,0);
if(u >= l && u <= r) ans = ans || dfs(u,1);
if(ans)return ans;
if(node >= l && node <= r && u <= r)ans = ans || dfs(u,1);
}
if(ans)return ans;
}
return ans;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
int Q = S.size();
int M = X.size();
vector<int> ans(Q,0);
for(int i=0;i<M;i++){
gr[X[i]].push_back(Y[i]);
gr[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++){
memset(vis,0,sizeof vis);
memset(pre,0,sizeof pre);
e = E[i], l = L[i], r = R[i];
ans[i] = dfs(S[i],0);
}
return ans;
}
/*
run werewolf 03.in 03.out
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
6092 KB |
Output is correct |
2 |
Correct |
8 ms |
6092 KB |
Output is correct |
3 |
Correct |
8 ms |
6092 KB |
Output is correct |
4 |
Correct |
9 ms |
6168 KB |
Output is correct |
5 |
Correct |
8 ms |
6140 KB |
Output is correct |
6 |
Correct |
9 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
6092 KB |
Output is correct |
8 |
Correct |
9 ms |
6148 KB |
Output is correct |
9 |
Correct |
9 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
6092 KB |
Output is correct |
2 |
Correct |
8 ms |
6092 KB |
Output is correct |
3 |
Correct |
8 ms |
6092 KB |
Output is correct |
4 |
Correct |
9 ms |
6168 KB |
Output is correct |
5 |
Correct |
8 ms |
6140 KB |
Output is correct |
6 |
Correct |
9 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
6092 KB |
Output is correct |
8 |
Correct |
9 ms |
6148 KB |
Output is correct |
9 |
Correct |
9 ms |
6092 KB |
Output is correct |
10 |
Correct |
326 ms |
6556 KB |
Output is correct |
11 |
Correct |
284 ms |
6508 KB |
Output is correct |
12 |
Correct |
151 ms |
6752 KB |
Output is correct |
13 |
Correct |
276 ms |
6476 KB |
Output is correct |
14 |
Correct |
258 ms |
6508 KB |
Output is correct |
15 |
Correct |
603 ms |
6684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4035 ms |
36220 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
6092 KB |
Output is correct |
2 |
Correct |
8 ms |
6092 KB |
Output is correct |
3 |
Correct |
8 ms |
6092 KB |
Output is correct |
4 |
Correct |
9 ms |
6168 KB |
Output is correct |
5 |
Correct |
8 ms |
6140 KB |
Output is correct |
6 |
Correct |
9 ms |
6092 KB |
Output is correct |
7 |
Correct |
10 ms |
6092 KB |
Output is correct |
8 |
Correct |
9 ms |
6148 KB |
Output is correct |
9 |
Correct |
9 ms |
6092 KB |
Output is correct |
10 |
Correct |
326 ms |
6556 KB |
Output is correct |
11 |
Correct |
284 ms |
6508 KB |
Output is correct |
12 |
Correct |
151 ms |
6752 KB |
Output is correct |
13 |
Correct |
276 ms |
6476 KB |
Output is correct |
14 |
Correct |
258 ms |
6508 KB |
Output is correct |
15 |
Correct |
603 ms |
6684 KB |
Output is correct |
16 |
Execution timed out |
4035 ms |
36220 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |