Submission #1220283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220283		boclobanchat	늑대인간 (IOI18_werewolf)	C++20	0 / 100	395 ms	73972 KiB

werewolf

#include"werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
struct dsutree
{
	int sp[MAXN][20],dis[MAXN],dsu[MAXN];
	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;
		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);
		}
	}
	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;
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);
	vector<int> ans;
	for(int i=0;i<q;i++) if(a.lca(S[i],E[i])>R[i]&&b.lca(S[i],E[i])<L[i]) ans.push_back(0);
	else ans.push_back(1);
	return ans;
}

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