Submission #1020771

#TimeUsernameProblemLanguageResultExecution timeMemory
1020771JakobZorzWerewolf (IOI18_werewolf)C++17
15 / 100
4030 ms29908 KiB
#include"werewolf.h" #include<queue> using namespace std; int n,m,q; vector<int>nodes[200000]; vector<bool>reachable1(int s,int t){ vector<bool>vis(n); queue<int>q; q.push(s); while(q.size()){ int node=q.front(); q.pop(); if(vis[node]||node>t) continue; vis[node]=true; for(int ne:nodes[node]) q.push(ne); } return vis; } vector<bool>reachable2(int s,int t){ vector<bool>vis(n); queue<int>q; q.push(s); while(q.size()){ int node=q.front(); q.pop(); if(vis[node]||node<t) continue; vis[node]=true; for(int ne:nodes[node]) q.push(ne); } return vis; } 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=(int)X.size(); q=(int)S.size(); for(int i=0;i<n;i++){ nodes[i].clear(); } for(int i=0;i<m;i++){ nodes[X[i]].push_back(Y[i]); nodes[Y[i]].push_back(X[i]); } vector<int>res(q); for(int i=0;i<q;i++){ vector<bool>v1=reachable2(S[i],L[i]); vector<bool>v2=reachable1(E[i],R[i]); for(int j=0;j<n;j++) if(v1[j]&&v2[j]) res[i]=1; } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...