Submission #1220508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220508		boclobanchat	Werewolf (IOI18_werewolf)	C++20	100 / 100	356 ms	103812 KiB

werewolf

#include"werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct query { int l,r,he,pos; };
struct dsutree
{
	int sp[MAXN][20],dis[MAXN],dsu[MAXN],eul[MAXN],L[MAXN],R[MAXN],tdfs=0;
	vector<int> ds[MAXN];
	int root(int i)
	{
		if(!dsu[i]) return i;
		return dsu[i]=root(dsu[i]);
	}
	void merge(int i,int j,bool ck)
	{
		i++,j++;
		if((i=root(i))==(j=root(j))) return ;
		if((i>j)^(!ck)) swap(i,j);
		dsu[j]=i,ds[i-1].push_back(j-1);
	}
	void dfs(int i,int pre)
	{
		sp[i][0]=pre,L[i]=++tdfs,eul[tdfs]=i;
		for(int j=1;j<=18;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
		for(auto v:ds[i])
		{
			dis[v]=dis[i]+1;
			dfs(v,i);
		}
		R[i]=tdfs;
	}
	int lca(int a,int b)
	{
		int x=dis[a],y=dis[b],m=min(x,y);
		for(int i=18;i+1;i--)
		{
			if((x-m)&(1<<i)) a=sp[a][i];
			if((y-m)&(1<<i)) b=sp[b][i];
		}
		if(a==b) return a;
		for(int i=18;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
		return sp[a][0];
	}
};
dsutree a,b;
int fen[MAXN],sum[MAXN],pos[MAXN];
vector<query> vi[MAXN];
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
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 m=X.size(),q=S.size();
	vector< vector<int> > ds(n);
	for(int i=0;i<m;i++)
	{
		if(X[i]>Y[i]) swap(X[i],Y[i]);
		ds[Y[i]].push_back(X[i]);
	}
	for(int i=0;i<n;i++) 
	{
		for(auto v:ds[i]) a.merge(i,v,false);
		ds[i].clear();
	}
	a.dfs(n-1,n-1);
	for(int i=0;i<m;i++) ds[X[i]].push_back(Y[i]);
	for(int i=n-1;i+1;i--) for(auto v:ds[i]) b.merge(i,v,true);
	b.dfs(0,0);
	for(int i=0;i<n;i++) pos[b.L[i]]=a.L[i];
	vector<int> ans;
	for(int i=0;i<q;i++)
	{
		int pl=S[i],pr=E[i];
		for(int j=18;j+1;j--)
		{
			if(b.sp[pl][j]>=L[i]) pl=b.sp[pl][j];
			if(a.sp[pr][j]<=R[i]) pr=a.sp[pr][j];
		}
		vi[b.L[pl]-1].push_back({a.L[pr],a.R[pr],-1,i});
		vi[b.R[pl]].push_back({a.L[pr],a.R[pr],1,i});
	}
	for(int i=1;i<=n;i++)
	{
		update(pos[i],n,1);
		for(auto v:vi[i]) sum[v.pos]+=v.he*(get(v.r)-get(v.l-1));
	}
	for(int i=0;i<q;i++) ans.push_back(sum[i]>0);
	return ans;
}

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