| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 122952 | medk | Werewolf (IOI18_werewolf) | C++14 | 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 <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
struct query
{
int e,s,l,r;
};
vector<vector<int>> g;
vector<int> ln;
vector<pair<int,query>> q,q2;
vector<pair<int,int>> lrng, rrng;
vector<int> ord;
vector<bool> is1, is2;
vector<pair<int,int>> par1,par2;
vector<pair<int,int>> rng1,rng2;
void makeline(int v, int par)
{
ord[v]=int(ln.size());
ln.pb(v);
for(int x:g[v])
if(x!=par) makeline(x,v);
}
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> ret;
int m=X.size(), Q=S.size();
g.resize(n);
ord.resize(n);
unordered_set<int> elim;
for(int i=0;i<n;++i) is1.pb(0), is2.pb(0), par1.pb({i,i}), par2.pb({i,i}), elim.insert(i);
for(int i=0;i<m;i++)
{
int x=X[i], y=Y[i];
g[x].pb(y);
g[y].pb(x);
if(g[x].size()==2) elim.erase(x);
if(g[y].size()==2) elim.erase(y);
}
makeline(*elim.begin(),-1);
for(int i=0;i<Q;i++)
{
rng1.pb({-1,-1}), rng2.pb({-1,-1});
int a=S[i], b=E[i], c=L[i], d=R[i];
q.pb({i,query{a,b,c,d}});
q2.pb({i,query{a,b,c,d}});
}
sort(q.begin(),q.end(),[ ](const pair<int,query>& left, const pair<int,query>& right){return left.y.r < right.y.r;});
sort(q2.begin(),q2.end(),[ ](const pair<int,query>& left, const pair<int,query>& right){return left.y.l > right.y.l;});
int k=0;
for(int i=0;i<n;i++)
{
int j=ord[i];
is1[j]=1;
if(j>0)
{
if(is1[j-1])
{
int id=j-1;
while(par1[id].x!=id) id=par1[id].x;
par1[j].x=id;
}
}
if(j<n-1)
{
if(is1[j+1])
{
int id=j+1;
while(par1[id].y!=id) id=par1[id].y;
par1[j].y=id;
}
}
if(j>0)
{
if(is1[j-1])
{
id=j;
while(par1[id].y!=id) id=par1[id].y;
par1[j-1].y=id;
}
}
if(j<n-1)
{
if(is1[j+1])
{
int id=j;
while(par1[id].x!=id) id=par1[id].x;
par1[j+1].x=id;
}
}
while(k<Q && q[k].y.r==i)
{
int id=ord[q[k].y.s];
int lft=par1[id].x;
while(par1[lft].x!=lft) lft=par1[lft].x;
int rgt=par1[id].y;
while(par1[rgt].y!=rgt) rgt=par1[rgt].y;
rng1[q[k].x]={lft,rgt};
k++;
}
}
k=0;
for(int i=n-1;i>=0;i--)
{
int j=ord[i];
is2[j]=1;
if(j>0)
{
if(is2[j-1])
{
int id=j-1;
while(par2[id].x!=id) id=par2[id].x;
par2[j].x=id;
}
}
if(j<n-1)
{
if(is2[j+1])
{
int id=j+1;
while(par2[id].y!=id) id=par2[id].y;
par2[j].y=id;
}
}
if(j>0)
{
if(is2[j-1])
{
id=j;
while(par2[id].y!=id) id=par2[id].y;
par2[j-1].y=id;
}
}
if(j<n-1)
{
if(is2[j+1])
{
int id=j;
while(par2[id].x!=id) id=par2[id].x;
par2[j+1].x=id;
}
}
while(k<Q && q2[k].y.l==i)
{
int id=ord[q2[k].y.e];
int lft=par2[id].x;
while(par2[lft].x!=lft) lft=par2[lft].x;
int rgt=par2[id].y;
while(par2[rgt].y!=rgt) rgt=par2[rgt].y;
rng2[q2[k].x]={lft,rgt};
k++;
}
}
sort(q.begin(),q.end(), [ ](const pair<int,query>& left, const pair<int,query>& right){return left.x < right.x;});
for(int i=0;i<Q;i++)
{
int l1=rng1[i].x, r1=rng1[i].y, l2=rng2[i].x, r2=rng2[i].y;
if(l2>r1 || l1>r2) ret.pb(0);
else
{
int l=max(l1,l2), r=min(r1,r2);
bool flag=0;
for(int k=min(l,r);k<=max(l,r);k++)
{
if(ln[k]!=q[i].y.e && ln[k]!=q[i].y.s)
{
flag=1; break;
}
}
if(flag) ret.pb(1);
else ret.pb(0);
}
}
return ret;
}