oj.uz

Submission #702999

# Submission time Handle Problem Language Result Execution time Memory
702999 2023-02-25T12:54:40 Z jamezzz Amusement Park (JOI17_amusement_park) C++17
100 / 100
 44 ms 16584 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;
		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;
			if(v[0].size()==60)break;
			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;
			if(v[0].size()==60)break;
			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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1800 KB Output is correct
2 Correct 2 ms 1804 KB Output is correct
3 Correct 2 ms 2060 KB Output is correct
4 Correct 2 ms 1796 KB Output is correct
5 Correct 2 ms 1792 KB Output is correct
6 Correct 2 ms 1792 KB Output is correct
7 Correct 2 ms 2064 KB Output is correct
8 Correct 2 ms 1928 KB Output is correct
9 Correct 2 ms 1940 KB Output is correct
10 Correct 2 ms 1864 KB Output is correct
11 Correct 5 ms 2136 KB Output is correct
12 Correct 2 ms 1736 KB Output is correct
13 Correct 2 ms 2064 KB Output is correct
14 Correct 2 ms 2060 KB Output is correct
15 Correct 2 ms 1996 KB Output is correct
16 Correct 3 ms 2168 KB Output is correct
17 Correct 2 ms 1940 KB Output is correct
18 Correct 2 ms 2064 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9268 KB Output is correct
2 Correct 38 ms 9688 KB Output is correct
3 Correct 40 ms 9660 KB Output is correct
4 Correct 30 ms 8624 KB Output is correct
5 Correct 32 ms 12340 KB Output is correct
6 Correct 32 ms 9832 KB Output is correct
7 Correct 30 ms 10492 KB Output is correct
8 Correct 31 ms 9820 KB Output is correct
9 Correct 31 ms 10280 KB Output is correct
10 Correct 39 ms 8660 KB Output is correct
11 Correct 44 ms 8752 KB Output is correct
12 Correct 27 ms 8032 KB Output is correct
13 Correct 27 ms 7948 KB Output is correct
14 Correct 30 ms 8424 KB Output is correct
15 Correct 33 ms 8704 KB Output is correct
16 Correct 32 ms 8788 KB Output is correct
17 Correct 30 ms 8756 KB Output is correct
18 Correct 31 ms 8624 KB Output is correct
19 Correct 30 ms 8648 KB Output is correct
20 Correct 27 ms 12584 KB Output is correct
21 Correct 30 ms 12548 KB Output is correct
22 Correct 30 ms 9944 KB Output is correct
23 Correct 31 ms 10740 KB Output is correct
24 Correct 31 ms 10228 KB Output is correct
25 Correct 32 ms 10620 KB Output is correct
26 Correct 30 ms 10092 KB Output is correct
27 Correct 32 ms 10088 KB Output is correct
28 Correct 31 ms 10344 KB Output is correct
29 Correct 27 ms 10052 KB Output is correct
30 Correct 30 ms 10288 KB Output is correct
31 Correct 2 ms 1772 KB Output is correct
32 Correct 2 ms 1804 KB Output is correct
33 Correct 2 ms 1864 KB Output is correct
34 Correct 2 ms 1804 KB Output is correct
35 Correct 2 ms 1800 KB Output is correct
36 Correct 2 ms 1804 KB Output is correct
37 Correct 2 ms 1808 KB Output is correct
38 Correct 2 ms 1796 KB Output is correct
39 Correct 2 ms 1792 KB Output is correct
40 Correct 2 ms 1804 KB Output is correct
41 Correct 2 ms 1800 KB Output is correct
42 Correct 2 ms 1864 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1800 KB Output is correct
2 Correct 3 ms 1804 KB Output is correct
3 Correct 2 ms 1804 KB Output is correct
4 Correct 6 ms 4148 KB Output is correct
5 Correct 7 ms 4284 KB Output is correct
6 Correct 7 ms 4152 KB Output is correct
7 Correct 7 ms 4216 KB Output is correct
8 Correct 6 ms 4140 KB Output is correct
9 Correct 31 ms 16532 KB Output is correct
10 Correct 30 ms 16584 KB Output is correct
11 Correct 28 ms 16492 KB Output is correct
12 Correct 2 ms 1804 KB Output is correct
13 Correct 2 ms 1860 KB Output is correct
14 Correct 2 ms 1804 KB Output is correct
15 Correct 1 ms 1792 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9712 KB Output is correct
2 Correct 38 ms 9712 KB Output is correct
3 Correct 37 ms 9512 KB Output is correct
4 Correct 28 ms 8656 KB Output is correct
5 Correct 35 ms 14132 KB Output is correct
6 Correct 32 ms 10532 KB Output is correct
7 Correct 30 ms 11016 KB Output is correct
8 Correct 32 ms 10116 KB Output is correct
9 Correct 33 ms 10760 KB Output is correct
10 Correct 41 ms 8640 KB Output is correct
11 Correct 39 ms 8728 KB Output is correct
12 Correct 27 ms 7952 KB Output is correct
13 Correct 27 ms 7916 KB Output is correct
14 Correct 27 ms 8400 KB Output is correct
15 Correct 30 ms 8756 KB Output is correct
16 Correct 34 ms 8744 KB Output is correct
17 Correct 32 ms 8612 KB Output is correct
18 Correct 30 ms 8724 KB Output is correct
19 Correct 31 ms 8740 KB Output is correct
20 Correct 32 ms 12720 KB Output is correct
21 Correct 27 ms 12552 KB Output is correct
22 Correct 30 ms 10804 KB Output is correct
23 Correct 30 ms 10024 KB Output is correct
24 Correct 30 ms 10056 KB Output is correct
25 Correct 30 ms 10124 KB Output is correct
26 Correct 30 ms 10072 KB Output is correct
27 Correct 31 ms 10800 KB Output is correct
28 Correct 31 ms 10076 KB Output is correct
29 Correct 27 ms 10000 KB Output is correct
30 Correct 30 ms 9704 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9664 KB Output is correct
2 Correct 39 ms 9668 KB Output is correct
3 Correct 37 ms 9516 KB Output is correct
4 Correct 30 ms 8632 KB Output is correct
5 Correct 32 ms 15152 KB Output is correct
6 Correct 31 ms 9780 KB Output is correct
7 Correct 35 ms 10656 KB Output is correct
8 Correct 32 ms 10348 KB Output is correct
9 Correct 31 ms 11000 KB Output is correct
10 Correct 39 ms 8656 KB Output is correct
11 Correct 39 ms 8688 KB Output is correct
12 Correct 28 ms 8000 KB Output is correct
13 Correct 27 ms 7916 KB Output is correct
14 Correct 27 ms 8296 KB Output is correct
15 Correct 31 ms 8752 KB Output is correct
16 Correct 30 ms 8736 KB Output is correct
17 Correct 32 ms 8716 KB Output is correct
18 Correct 30 ms 8728 KB Output is correct
19 Correct 31 ms 8728 KB Output is correct
20 Correct 28 ms 12680 KB Output is correct
21 Correct 27 ms 12452 KB Output is correct
22 Correct 31 ms 10572 KB Output is correct
23 Correct 32 ms 10544 KB Output is correct
24 Correct 31 ms 10504 KB Output is correct
25 Correct 31 ms 10560 KB Output is correct
26 Correct 30 ms 10024 KB Output is correct
27 Correct 31 ms 11272 KB Output is correct
28 Correct 32 ms 11044 KB Output is correct
29 Correct 27 ms 10252 KB Output is correct
30 Correct 27 ms 9700 KB Output is correct
31 Correct 2 ms 1804 KB Output is correct
32 Correct 2 ms 2044 KB Output is correct
33 Correct 2 ms 1864 KB Output is correct
34 Correct 2 ms 1804 KB Output is correct
35 Correct 2 ms 1804 KB Output is correct
36 Correct 2 ms 1804 KB Output is correct
37 Correct 2 ms 1804 KB Output is correct
38 Correct 2 ms 1740 KB Output is correct
39 Correct 3 ms 1792 KB Output is correct
40 Correct 2 ms 1804 KB Output is correct
41 Correct 2 ms 1864 KB Output is correct
42 Correct 2 ms 1800 KB Output is correct