| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1350403 | kokoxuya | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
#define pipi pair<pii,pii>
void dfs(int cn, int num, vector<pii>&nummys, vector<int>&corr, vector<bool>&visited)
{
visited[cn]=true;
nummys.pb(mp(cn,num));
corr[cn]=num;num++;
for(int to:adjlist[cn])
{
if(visited[to])continue;
dfs(to,num,nummys,corr,visited);
}
}
vector<int> check_validity(int N,vector<int> X, vector<int> Y,vector<int> S,vector<int> E,vector<int> L, vector<int> R)
{
int n=N,m=X.size(),q=S.size();
vector<int>corr(n);
vector<vector<int>>adjlist(n);
for(int a=0;a<m;a++)
{
adjlist[X[a]].pb(Y[a]);
adjlist[Y[a]].pb(X[a]);
}
int star;
for(int a=0;a<n;a++){if(adjlist[a].size()==1)star=a;}
vector<bool>visited(n,false);
vector<pii>nummys;
dfs(star,1,nummys,corr,visited);
sort(nummys.begin(),nummys.end(),greater<pii>());
for(int i=0;i<q;i++)
{
S[i]=corr[S[i]];
E[i]=corr[E[i]];
if(S[i]>E[i])swap(S[i],E[i]);
}
priority_queue<pii>ls;
priority_queue<pii,vector<pii>,greater<pii>>rs;
for(int i=0;i<q;i++)
{
ls.push(mp(L[i],i));
rs.push(mp(R[i],i));
}
vector<pipi>urans(q);
for(int i=0;i<2;i++)
{
set<pii>ranges;
for(pii curr:nummys)
{
int cn=curr.ss;
ranges.insert(mp(cn,cn));
auto x=ranges.find(mp(cn,cn));
auto y=ranges.end(),z=ranges.end();
if(x!=ranges.begin()){y=prev(x);}
if(x!=ranges.end()){z=next(x);}
if(y!=ranges.end())
{
if((*y).ss==cn-1)
{
pii t1=*next(y),t2=*y;
ranges.erase(next(y));ranges.erase(y);
ranges.insert(mp(t2.ff,t1.ss));
}
}
if(z!=ranges.end())
{
if((*z).ff==cn+1)
{
pii t1=*prev(z),t2=*z;
ranges.erase(prev(z));ranges.erase(z);
ranges.insert(mp(t1.ff,t2.ss));
}
}
if(i)
{
while(!rs.empty()&&rs.top().ff==curr.ff)
{
int qno=rs.top().ss;
int k=s[qno],kk=e[qno];
ls.pop();
auto j=ranges.upper_bound(mp(k+1,0));
if(j==ranges.begin()||(*prev(j)).ss<k){urans[qno].ff.ss=-1;}
else
{
urans[qno].ff.ss=(*(prev(j))).ss;
}
auto j=ranges.upper_bound(mp(kk+1,0));
if(j==ranges.begin()||(*prev(j)).ss<kk){urans[qno].ss.ss=-1;}
else
{
urans[qno].ss.ss=(*(prev(j))).ff;
}
}
}
else
{
while(!ls.empty()&&ls.top().ff==curr.ff)
{
int qno=ls.top().ss;
int k=s[qno],kk=e[qno];
ls.pop();
auto j=ranges.upper_bound(mp(k+1,0));
if(j==ranges.begin()||(*prev(j)).ss<k){urans[qno].ff.ff=-1;}
else
{
urans[qno].ff.ff=(*(prev(j))).ss;
}
auto j=ranges.upper_bound(mp(kk+1,0));
if(j==ranges.begin()||(*prev(j)).ss<kk){urans[qno].ss.ff=-1;}
else
{
urans[qno].ss.ff=(*(prev(j))).ff;
}
}
}
}
reverse(nummys.begin(),nummys.end());
}
vector<int>ans;
for(int i=0;i<q;i++)
{
bool troo=false;
pii f1=urans[i],f2=urans[i];
if(f1.ff!=-1&&(f2.ss!=-1&&f1.ff>=f2.ss))troo=true;
if(f1.ss!=-1&&(f2.ff!=-1&&f1.ff>=f2.ss))troo=true;
ans.pb(troo);
}
return ans;
}