| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 611416 | terrasphere | 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 <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
vector<vector<int>> edges;
vector<int> linear;
const int INF=1e9;
int index[222222];
int cnt[222222];
bool visited[222222];
bool visited1[3333];
bool visited2[3333];
vector<int> max_tree,min_tree;
void init(int node,int start,int end)
{
if(start==end)
{
max_tree[node]=linear[start];
min_tree[node]=linear[start];
return;
}
init(node*2,start,(start+end)/2);
init(node*2+1,(start+end)/2+1,end);
max_tree[node]=max(max_tree[node*2],max_tree[node*2+1]);
min_tree[node]=min(min_tree[node*2],min_tree[node*2+1]);
return;
}
int max_query(int node,int start,int end,int left,int right)
{
if(start>right || end<left)
return -INF;
if(left<=start && end<=right)
return max_tree[node];
return max(max_query(node*2,start,(start+end)/2,left,right),max_query(node*2+1,(start+end)/2+1,end,left,right));
}
int min_query(int node,int start,int end,int left,int right)
{
if(start>right || end<left)
return INF;
if(left<=start && end<=right)
return min_tree[node];
return min(min_query(node*2,start,(start+end)/2,left,right),min_query(node*2+1,(start+end)/2+1,end,left,right));
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R)
{
vector<int> result;
int n,m,Q;
n=N;
m=X.size();
Q=S.size();
edges.resize(n);
for(int j=0;j<m;j++)
{
cnt[X[j]]++;
cnt[Y[j]]++;
edges[X[j]].push_back(Y[j]);
edges[Y[j]].push_back(X[j]);
}
for(int j=0;j<m;j++)
{
if(cnt[j]==1)
{
linear.push_back(j);
break;
}
}
if(n<=3000 && m<=6000 && Q<=3000)
{
for(int i=0;i<Q;i++)
{
memset(visited1,false,sizeof(visited1));
memset(visited2,false,sizeof(visited2));
queue<int> q;
q.push(S[i]);
visited1[S[i]]=true;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int next: edges[cur])
{
if(visited1[next])
continue;
if(next<L[i])
continue;
visited1[next]=true;
q.push(next);
}
}
q.push(E[i]);
visited2[E[i]]=true;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int next: edges[cur])
{
if(visited2[next])
continue;
if(next>R[i])
continue;
visited2[next]=true;
q.push(next);
}
}
int answer=0;
for(int i=0;i<n;i++)
if(visited1[i] && visited2[i])
answer=1;
result.push_back(answer);
}
}
else
{
queue<int> q;
visited[linear[0]]=true;
q.push(linear[0]);
index[linear[0]]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int next: edges[cur])
{
if(visited[next])
continue;
q.push(next);
linear.push_back(next);
index[next]=linear.size();
visited[next]=true;
}
}
max_tree.resize(4*n);
min_tree.resize(4*n);
init(1,0,n-1);
for(int i=0;i<Q;i++)
{
int s,e,l,r;
s=index[S[i]];
e=index[E[i]];
l=L[i];
r=R[i];
int sl,sr,el,er;
int high=s;
int low=0;
int mid;
sl=s;
sr=s;
el=e;
er=e;
while(low<=high)
{
mid=(high+low)/2;
if(min_query(1,0,n-1,mid,s)>=l)
{
sl=mid;
high=mid-1;
}
else
low=mid+1;
}
high=n-1;
low=s;
while(low<=high)
{
mid=(high+low)/2;
if(min_query(1,0,n-1,s,mid)>=l)
{
sr=mid;
low=mid+1;
}
else
high=mid-1;
}
high=e;
low=0;
while(low<=high)
{
mid=(high+low)/2;
if(max_query(1,0,n-1,mid,e)<=r)
{
el=mid;
high=mid-1;
}
else
low=mid+1;
}
high=n-1;
low=e;
while(low<=high)
{
mid=(high+low)/2;
if(max_query(1,0,n-1,e,mid)<=r)
{
er=mid;
low=mid+1;
}
else
high=mid-1;
}
if(er<sl || el>sr)
result.push_back(0);
else
result.push_back(1);
}
}
return result;
}