Submission #702981

#	Time	Username	Problem	Language	Result	Execution time	Memory
702981		jamezzz	Amusement Park (JOI17_amusement_park)	C++17	0 / 100	28 ms	7108 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 10005
#define pb push_back

namespace joi{
	int num[maxn],par[maxn],rnk[maxn];
	bool in[maxn],vis[maxn];
	vector<int> v[maxn],AL[maxn];
	vector<pair<int,int>> edges;
	void dfs(int u,int p,vector<int> stuff);
	void proc();
	int fp(int i);
	void join(int x,int y);
}

int joi::fp(int i){
	return (par[i]==i)?i:par[i]=fp(par[i]);
}
void joi::join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
}

void joi::dfs(int u,int p,vector<int> stuff){
	vis[u]=true;
	bool have=false;
	for(int i:stuff){
		if(i==u)have=true;
	}
	if(!have){
		int rem=-1;
		for(int i:stuff)in[i]=true;
		for(int i:stuff){
			int deg=0;
			for(int j:AL[i])deg+=in[j];
			if(deg==1&&i!=p){
				rem=i;
				break;
			}
		}
		for(int i:stuff)in[i]=false;
		num[u]=num[rem];
		vector<int> tmp;
		for(int i:stuff){
			if(i!=rem)tmp.pb(i);
		}
		tmp.pb(u);
		swap(tmp,stuff);
	}
	v[u]=stuff;
	for(int v:AL[u]){
		if(v!=p&&!vis[v])dfs(v,u,stuff);
	}
}

void joi::proc(){
	for(int i=0;i<maxn;++i){
		par[i]=i;rnk[i]=0;
	}
	for(auto[a,b]:edges){
		if(fp(a)==fp(b))continue;
		AL[a].pb(b);
		AL[b].pb(a);
		join(a,b);
	}
	queue<int> q;
	q.push(0);
	v[0].pb(0);
	in[0]=true;
	while(v[0].size()!=60){
		int u=q.front();
		q.pop();
		for(int x:AL[u]){
			if(in[x])continue;
			v[0].pb(x);
			in[x]=true;
			q.push(x);
		}
	}
	for(int i=0;i<60;++i){
		num[v[0][i]]=i;
		in[v[0][i]]=false;
	}
	dfs(0,-1,v[0]);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	for(int i=0;i<N;++i){
		joi::vis[i]=false;
		joi::AL[i].clear();
	}
	joi::edges.clear();
	for(int i=0;i<M;++i){
		joi::edges.push_back({A[i],B[i]});
	}
	joi::proc();
	for(int i=0;i<N;++i){
		//printf("%d ",joi::num[i]);
		if(X&(1ll<<joi::num[i]))MessageBoard(i,1);
		else MessageBoard(i,0);
	}
	//printf("\n");
	//for(int i=0;i<N;++i){
		//printf("%d: ",i);
		//for(int x:joi::v[i])printf("%d ",x);
		//printf("\n");
	//}
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 10005
#define pb push_back

namespace ioi{
	int num[maxn],par[maxn],rnk[maxn];
	bool in[maxn],vis[maxn];
	vector<int> v[maxn],AL[maxn];
	vector<pair<int,int>> edges;
	void dfs(int u,int p,vector<int> stuff);
	void proc();
	int fp(int i);
	void join(int x,int y);
}

int ioi::fp(int i){
	return (par[i]==i)?i:par[i]=fp(par[i]);
}
void ioi::join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])par[x]=y;
	else par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
}

void ioi::dfs(int u,int p,vector<int> stuff){
	vis[u]=true;
	bool have=false;
	for(int i:stuff){
		if(i==u)have=true;
	}
	if(!have){
		int rem=-1;
		for(int i:stuff)in[i]=true;
		for(int i:stuff){
			int deg=0;
			for(int j:AL[i])deg+=in[j];
			if(deg==1&&i!=p){
				rem=i;
				break;
			}
		}
		for(int i:stuff)in[i]=false;
		num[u]=num[rem];
		vector<int> tmp;
		for(int i:stuff){
			if(i!=rem)tmp.pb(i);
		}
		tmp.pb(u);
		swap(tmp,stuff);
	}
	v[u]=stuff;
	for(int v:AL[u]){
		if(v!=p&&!vis[v])dfs(v,u,stuff);
	}
}

void ioi::proc(){
	for(int i=0;i<maxn;++i){
		par[i]=i;rnk[i]=0;
	}
	for(auto[a,b]:edges){
		if(fp(a)==fp(b))continue;
		AL[a].pb(b);
		AL[b].pb(a);
		join(a,b);
	}
	queue<int> q;
	q.push(0);
	v[0].pb(0);
	in[0]=true;
	while(v[0].size()!=60){
		int u=q.front();
		q.pop();
		for(int x:AL[u]){
			if(in[x])continue;
			v[0].pb(x);
			in[x]=true;
			q.push(x);
		}
	}
	for(int i=0;i<60;++i){
		num[v[0][i]]=i;
		in[v[0][i]]=false;
	}
	dfs(0,-1,v[0]);
}

int write[maxn];

void dfs2(int u,int p){
	for(int v:ioi::AL[u]){
		if(v==p||!ioi::in[v])continue;
		write[v]=Move(v);
		dfs2(v,u);
		Move(u);
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	assert(false);
	for(int i=0;i<N;++i){
		ioi::vis[i]=false;
		ioi::AL[i].clear();
	}
	ioi::edges.clear();
	for(int i=0;i<M;++i){
		ioi::edges.push_back({A[i],B[i]});
	}
	ioi::proc();
	write[P]=V;
	for(int i:ioi::v[P])ioi::in[i]=true;
	dfs2(P,-1);
	long long ans=0;
	for(int i:ioi::v[P]){
		ans^=((long long)write[i]<<ioi::num[i]);
	}
	return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17