| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1021106 | JakobZorz | Werewolf (IOI18_werewolf) | C++17 | 0 ms | 0 KiB |
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>
#include<algorithm>
using namespace std;
int n,m,q;
vector<int>nodes[200000];
struct RMQ{
vector<vector<int>>table;
vector<int>lg2;
int n;
RMQ(vector<int>arr){
n=(int)arr.size();
table=vector<vector<int>>(20,vector<int>(n));
int curr=1;
lg2=vector<int>(n+1);
for(int i=2;i<=n;i++){
while((1<<curr)<=i)
curr++;
lg2[i]=curr-1;
}
table[0]=arr;
for(int p=1;p<20;p++){
for(int i=0;i+(1<<p)<=n;i++){
table[p][i]=max(table[p-1][i],table[p-1][i+(1<<(p-1))]);
}
}
}
int get(int l,int r){
if(l==r)
return 0;
int lg=lg2[r-l];
return max(table[lg][l],table[lg][r-(1<<lg)]);
}
};
struct Query{
int S,E,L,R;
int ans;
};
bool cmp(Query*a,Query*b){
return a->L>b->L;
}
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>line;
{
vector<int>comp(n);
vector<deque<int>>comps(n);
for(int i=0;i<n;i++){
set<int>to_add;
int curr_comp=i;
comps[i]=i;
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());
for(int k:comps[j])
comp[k]=curr_comp;
comps[i].push_back(i);
}
comps[i].push_front(i);
}
line=vector<int>(comps[comp[0]].begin(),comps[comp[0]].end());
}
vector<int>to_line(n);
for(int i=0;i<(int)line.size();i++){
to_line[line[i]]=i;
}
RMQ rmq=RMQ(line);
/*for(int i:line)
cout<<i<<" ";
cout<<"\n";*/
vector<Query*>qrs(q);
for(int i=0;i<q;i++){
qrs[i]=new Query;
qrs[i]->S=S[i];
qrs[i]->E=E[i];
qrs[i]->L=L[i];
qrs[i]->R=R[i];
qrs[i]->ans=0;
}
vector<Query*>srt=qrs;
sort(srt.begin(),srt.end(),cmp);
vector<int>comp(n);
vector<vector<int>>comps(n);
vector<set<int>>comps_line(n);
int r=n-1;
for(auto qry:srt){
while(r>=qry->L){
comp[r]=r;
comps[r]={r};
comps_line[r].insert(to_line[r]);
for(int ne:nodes[r]){
if(ne<r)
continue;
if(comp[ne]!=comp[r]){
comps[comp[r]].insert(comps[comp[r]].end(),comps[comp[ne]].begin(),comps[comp[ne]].end());
for(int i:comps_line[comp[ne]])
comps_line[r].insert(i);
for(int i:comps[comp[r]])
comp[i]=comp[r];
}
}
r--;
}
int rl,rr;
/*for(int j=0;j<(int)line.size();j++){
if(line[j]==qry->E){
//for(rr=j;rr<(int)line.size()&&line[rr]<=qry->R;rr++);
//for(rl=j;rl>=0&&line[rl]<=qry->R;rl--);
break;
}
}*/
{
int i=to_line[qry->E];
int l=i,r=(int)line.size();
while(l<r-1){
int mid=(l+r)/2;
if(rmq.get(i,mid+1)<=qry->R)
l=mid;
else
r=mid;
}
rr=r;
}
{
int i=to_line[qry->E];
int l=0,r=i;
while(l<r-1){
int mid=(l+r)/2;
if(rmq.get(mid,i)<=qry->R)
r=mid;
else
l=mid;
}
rl=l;
}
auto iter=comps_line[comp[qry->S]].lower_bound(rl+1);
if(iter!=comps_line[comp[qry->S]].end()&&*iter<rr)
qry->ans=1;
/*for(int i:comps_line[comp[qry->S]]){
if(rl<i&&i<rr)
qry->ans=1;
}*/
}
vector<int>res(q);
for(int i=0;i<q;i++)
res[i]=qrs[i]->ans;
return res;
}