답안 #702999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702999	2023-02-25T12:54:40 Z	jamezzz	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	44 ms	16584 KB

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;
			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");
	//}
}

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;
			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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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