This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
using namespace std;
int n,m,q;
vector<int>nodes[200000];
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>comp(n);
vector<vector<int>>comps(n);
for(int i=0;i<n;i++){
comps[i]={i};
set<int>to_add;
for(int ne:nodes[i]){
if(ne>i)
continue;
to_add.insert(comp[ne]);
}
for(int j:to_add){
comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
comps[i].push_back(i);
}
for(int j:comps[i])
comp[j]=i;
}
vector<int>line=comps[comp[0]];
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]);
vector<bool>v2(n);
for(int j=0;j<(int)line.size();j++){
if(line[j]==E[i]){
for(int k=j;k<n&&line[k]<=R[i];k++)
v2[line[k]]=true;
for(int k=j;k>=0&&line[k]<=R[i];k--)
v2[line[k]]=true;
break;
}
}
for(int j=0;j<n;j++)
if(v1[j]&&v2[j])
res[i]=1;
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |