oj.uz

Submission #702989

# Submission time Handle Problem Language Result Execution time Memory
702989 2023-02-25T12:05:37 Z jamezzz Amusement Park (JOI17_amusement_park) C++17
10 / 100
 44 ms 16348 KB 
#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;
		assert(rem!=-1);
		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::v[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");
	//}
}

#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) {
	for(int i=0;i<N;++i){
		ioi::vis[i]=false;
		ioi::AL[i].clear();
		ioi::v[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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1792 KB Output is correct
2 Correct 2 ms 1792 KB Output is correct
3 Correct 3 ms 2060 KB Output is correct
4 Correct 2 ms 1792 KB Output is correct
5 Correct 2 ms 1800 KB Output is correct
6 Runtime error 1 ms 1492 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 3408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1796 KB Output is correct
2 Correct 2 ms 1796 KB Output is correct
3 Correct 2 ms 1788 KB Output is correct
4 Correct 7 ms 4128 KB Output is correct
5 Correct 6 ms 4124 KB Output is correct
6 Correct 6 ms 4136 KB Output is correct
7 Correct 5 ms 4132 KB Output is correct
8 Correct 5 ms 4128 KB Output is correct
9 Correct 28 ms 16252 KB Output is correct
10 Correct 30 ms 16348 KB Output is correct
11 Correct 30 ms 16308 KB Output is correct
12 Correct 2 ms 1804 KB Output is correct
13 Correct 2 ms 1800 KB Output is correct
14 Correct 2 ms 1800 KB Output is correct
15 Correct 2 ms 1816 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 3464 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9260 KB Output is correct
2 Correct 40 ms 9132 KB Output is correct
3 Correct 44 ms 9220 KB Output is correct
4 Runtime error 7 ms 3024 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -