# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1043006 | 2024-08-03T17:42:39 Z | XJP12 | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef vector<vi> vvi ; vvi g; bitset<200005> vis; bitset<200005> vis1; bool ban=false; void dfs2(int u, int l){ if(u>l) return; vis1[u]=true; if(vis[u]==true && vis1[u]==true){ ban=true; } for(auto v: g[u]){ if(!vis1[v]){ dfs2(v,l); } } } void dfs1(int u, int l){ if(u<l) return; vis[u]=true; for(auto v: g[u]){ if(!vis[v]){ dfs1(v,l); } } } vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r){ int m = (int)x.size(); int q = (int)e.size(); vi ans(q,0); g.resize(n, vi()); for(int i=0; i<m; i++){ g[x[i]].push_back(y[i]); g[y[i]].push_back(x[i]); } for(int i=0; i<q; i++){ vis.reset(); vis1.reset(); bam==false; dfs1(s[i], l[i]); dfs2(e[i], r[i]); if(ban){ ans[i]=1; } } return ans; }