Submission #986400

#	Time	Username	Problem	Language	Result	Execution time	Memory
986400		Pyqe	Werewolf (IOI18_werewolf)	C++17	100 / 100	797 ms	158768 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n,m,dsu[200069],pst[200069],sbt[200069],pr[200069][18],cc[200069];
vector<long long> al[200069],al2[200069];
pair<pair<long long,long long>,long long> qq[200069];
pair<long long,long long> qs[200069];
multiset<long long> ms[200069];
bitset<200069> sq;

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

void bd(long long x)
{
	long long i,j,sz=al2[x].size(),l;
	
	n++;
	pst[x]=n;
	sbt[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al2[x][i];
		pr[l][0]=x;
		for(j=1;j<18;j++)
		{
			pr[l][j]=pr[pr[l][j-1]][j-1];
		}
		bd(l);
		sbt[x]+=sbt[l];
	}
}

void jo(long long x,long long y)
{
	multiset<long long>::iterator it;
	
	x=fd(x);
	y=fd(y);
	if(cc[x]<cc[y])
	{
		swap(x,y);
	}
	for(it=ms[y].begin();it!=ms[y].end();it++)
	{
		ms[x].insert(*it);
	}
	cc[x]+=cc[y];
	dsu[y]=x;
}

vector<int> check_validity(int on,vector<int> ka,vector<int> la,vector<int> sta,vector<int> fna,vector<int> lba,vector<int> rba)
{
	long long t=sta.size(),rr,i,j,k,l,w,sz,pz;
	multiset<long long>::iterator it;
	vector<int> v;
	
	n=on;
	m=ka.size();
	for(i=0;i<m;i++)
	{
		k=ka[i]+1;
		l=la[i]+1;
		al[k].push_back(l);
		al[l].push_back(k);
	}
	for(i=n;i;i--)
	{
		dsu[i]=i;
		sz=al[i].size();
		for(j=0;j<sz;j++)
		{
			l=al[i][j];
			if(l>i&&fd(l)!=i)
			{
				al2[i].push_back(fd(l));
				dsu[fd(l)]=i;
			}
		}
	}
	n=0;
	bd(1);
	for(rr=1;rr<=t;rr++)
	{
		qq[rr]={{sta[rr-1]+1,fna[rr-1]+1},lba[rr-1]+1};
		qs[rr]={rba[rr-1]+1,rr};
	}
	sort(qs+1,qs+t+1);
	for(i=0,rr=1;rr<=t;rr++)
	{
		k=qs[rr].fr;
		pz=qs[rr].sc;
		for(;i<k;)
		{
			i++;
			dsu[i]=i;
			cc[i]=1;
			ms[i].insert(pst[i]);
			sz=al[i].size();
			for(j=0;j<sz;j++)
			{
				l=al[i][j];
				if(l<i&&fd(l)!=fd(i))
				{
					jo(i,l);
				}
			}
		}
		k=qq[pz].fr.fr;
		l=qq[pz].fr.sc;
		w=qq[pz].sc;
		for(j=17;j+1;j--)
		{
			if(pr[k][j]>=w)
			{
				k=pr[k][j];
			}
		}
		it=ms[fd(l)].lower_bound(pst[k]);
		sq[pz]=it!=ms[fd(l)].end()&&*it<=pst[k]+sbt[k]-1;
	}
	for(rr=1;rr<=t;rr++)
	{
		v.push_back(sq[rr]);
	}
	return v;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51