Submission #565870

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
565870	2022-05-21T13:20:47 Z	errorgorn	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	505 ms	55452 KB

#include "Joi.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace{
	
int n,m;
vector<int> al[10005];
int id[10005];
vector<int> cc[100005];

bool vis[10005];
int IDX=0;

bitset<10005> has[10005];

void dfs(int i,int p){
	vis[i]=true;
	
	if (IDX<60){
		id[i]=IDX++;
		if (IDX==60){
			vector<int> v;
			rep(x,0,n) if (vis[x]) v.pub(x);
			for (auto it:v) cc[it]=v;
		}
	}
	else{
		//copy cc[p], remove one guy and add i
		cc[i]=cc[p];
		cc[i].pub(i);
		map<int,int> cnt;
		rep(x,0,sz(cc[i])) rep(y,x+1,sz(cc[i])) if (has[cc[i][x]][cc[i][y]]){
			cnt[x]++,cnt[y]++;
		}
		
		//for (auto [a,b]:cnt) cout<<a<<" "<<cc[i][a]<<" "<<b<<endl;
		
		for (auto [a,b]:cnt) if (b==1){
			cc[i].erase(cc[i].begin()+a);
			break;
		}
		
		set<int> ids;
		rep(x,0,60) ids.insert(x);
		rep(x,0,sz(cc[i])-1) ids.erase(id[cc[i][x]]);
		id[i]=*ids.begin();
	}
	
	for (auto it:al[i]) if (!vis[it]){
		has[it][i]=1;
		has[i][it]=1;
		dfs(it,i);
	}
}

}

void Joi(signed N, signed M, signed A[], signed B[], long long X, signed T) {
	n=N,m=M;
	rep(x,0,m){
		al[A[x]].pub(B[x]);
		al[B[x]].pub(A[x]);
	}
	
	dfs(0,-1);
	
	//rep(x,0,n){
		//for (auto it:cc[x]) cout<<it<<" "; cout<<endl;
	//}
	
	//rep(x,0,n) cout<<id[x]<<" "; cout<<endl;
	rep(x,0,n) MessageBoard(x,(X>>id[x])&1);
}

#include "Ioi.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace{
	
int n,m;
vector<int> al[10005];
int id[10005];
vector<int> cc[100005];

bool vis[10005];
int IDX=0;

bitset<10005> has[10005];

void dfs(int i,int p){
	vis[i]=true;
	
	if (IDX<60){
		id[i]=IDX++;
		if (IDX==60){
			vector<int> v;
			rep(x,0,n) if (vis[x]) v.pub(x);
			for (auto it:v) cc[it]=v;
		}
	}
	else{
		//copy cc[p], remove one guy and add i
		cc[i]=cc[p];
		cc[i].pub(i);
		map<int,int> cnt;
		rep(x,0,sz(cc[i])) rep(y,x+1,sz(cc[i])) if (has[cc[i][x]][cc[i][y]]){
			cnt[x]++,cnt[y]++;
		}
		
		//for (auto [a,b]:cnt) cout<<a<<" "<<cc[i][a]<<" "<<b<<endl;
		
		for (auto [a,b]:cnt) if (b==1){
			cc[i].erase(cc[i].begin()+a);
			break;
		}
		
		set<int> ids;
		rep(x,0,60) ids.insert(x);
		rep(x,0,sz(cc[i])-1) ids.erase(id[cc[i][x]]);
		id[i]=*ids.begin();
	}
	
	for (auto it:al[i]) if (!vis[it]){
		has[it][i]=1;
		has[i][it]=1;
		dfs(it,i);
	}
}

int k;
set<int> s;
int ans=0;

void dfs2(int i,int p){
	if (p!=-1) ans|=((int)Move(i))<<id[i];
	
	vis[i]=true;
	
	for (auto it:al[i]) if (!vis[it] && s.count(it)){
		dfs2(it,i);
	}
	
	if (p!=-1) ans|=((int)Move(p))<<id[p];
}

}

long long Ioi(signed N, signed M, signed A[], signed B[], signed P, signed V, signed T) {
	n=N,m=M,k=P;
	rep(x,0,m){
		al[A[x]].pub(B[x]);
		al[B[x]].pub(A[x]);
	}
	
	dfs(0,-1);
	
	memset(vis,false,sizeof(vis));
	s=set<int>(all(cc[k]));
	dfs2(k,-1);
	
	return ans;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6152 KB	Output is correct
2	Correct	9 ms	6432 KB	Output is correct
3	Correct	13 ms	7124 KB	Output is correct
4	Correct	5 ms	6156 KB	Output is correct
5	Correct	5 ms	6420 KB	Output is correct
6	Correct	8 ms	6680 KB	Output is correct
7	Correct	14 ms	7184 KB	Output is correct
8	Correct	13 ms	7180 KB	Output is correct
9	Correct	12 ms	6940 KB	Output is correct
10	Correct	8 ms	6416 KB	Output is correct
11	Correct	9 ms	6880 KB	Output is correct
12	Correct	4 ms	6160 KB	Output is correct
13	Correct	13 ms	7196 KB	Output is correct
14	Correct	14 ms	7180 KB	Output is correct
15	Correct	14 ms	7196 KB	Output is correct
16	Correct	14 ms	7196 KB	Output is correct
17	Correct	14 ms	7248 KB	Output is correct
18	Correct	13 ms	7152 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	421 ms	54892 KB	Output is correct
2	Correct	410 ms	55452 KB	Output is correct
3	Correct	416 ms	55228 KB	Output is correct
4	Correct	426 ms	51268 KB	Output is correct
5	Correct	398 ms	53192 KB	Output is correct
6	Correct	414 ms	52588 KB	Output is correct
7	Correct	409 ms	52656 KB	Output is correct
8	Correct	422 ms	53132 KB	Output is correct
9	Correct	417 ms	52968 KB	Output is correct
10	Correct	413 ms	51248 KB	Output is correct
11	Correct	399 ms	51312 KB	Output is correct
12	Correct	368 ms	47272 KB	Output is correct
13	Correct	388 ms	47172 KB	Output is correct
14	Correct	390 ms	49488 KB	Output is correct
15	Correct	434 ms	51092 KB	Output is correct
16	Correct	442 ms	51108 KB	Output is correct
17	Correct	413 ms	51156 KB	Output is correct
18	Correct	415 ms	51288 KB	Output is correct
19	Correct	430 ms	51324 KB	Output is correct
20	Correct	366 ms	53660 KB	Output is correct
21	Correct	378 ms	53028 KB	Output is correct
22	Correct	412 ms	52500 KB	Output is correct
23	Correct	412 ms	53140 KB	Output is correct
24	Correct	413 ms	52652 KB	Output is correct
25	Correct	409 ms	52928 KB	Output is correct
26	Correct	412 ms	53296 KB	Output is correct
27	Correct	405 ms	53120 KB	Output is correct
28	Correct	435 ms	53396 KB	Output is correct
29	Correct	370 ms	48820 KB	Output is correct
30	Correct	434 ms	50632 KB	Output is correct
31	Correct	9 ms	6428 KB	Output is correct
32	Correct	10 ms	6664 KB	Output is correct
33	Correct	14 ms	7180 KB	Output is correct
34	Correct	9 ms	6416 KB	Output is correct
35	Correct	7 ms	6164 KB	Output is correct
36	Correct	4 ms	6164 KB	Output is correct
37	Correct	4 ms	6156 KB	Output is correct
38	Correct	4 ms	6160 KB	Output is correct
39	Correct	4 ms	6156 KB	Output is correct
40	Correct	5 ms	6164 KB	Output is correct
41	Correct	6 ms	6404 KB	Output is correct
42	Correct	4 ms	6164 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6160 KB	Output is correct
2	Correct	6 ms	6184 KB	Output is correct
3	Correct	6 ms	6168 KB	Output is correct
4	Correct	61 ms	13648 KB	Output is correct
5	Correct	61 ms	13808 KB	Output is correct
6	Correct	61 ms	13736 KB	Output is correct
7	Correct	64 ms	13812 KB	Output is correct
8	Correct	62 ms	13776 KB	Output is correct
9	Correct	368 ms	55288 KB	Output is correct
10	Correct	374 ms	55252 KB	Output is correct
11	Correct	389 ms	55260 KB	Output is correct
12	Correct	4 ms	6164 KB	Output is correct
13	Correct	4 ms	6172 KB	Output is correct
14	Correct	4 ms	6164 KB	Output is correct
15	Correct	4 ms	6164 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	54928 KB	Output is correct
2	Correct	413 ms	55248 KB	Output is correct
3	Correct	417 ms	55216 KB	Output is correct
4	Correct	423 ms	51172 KB	Output is correct
5	Correct	418 ms	54596 KB	Output is correct
6	Correct	414 ms	53216 KB	Output is correct
7	Correct	419 ms	52932 KB	Output is correct
8	Correct	395 ms	52156 KB	Output is correct
9	Correct	411 ms	52620 KB	Output is correct
10	Correct	395 ms	51244 KB	Output is correct
11	Correct	391 ms	51336 KB	Output is correct
12	Correct	390 ms	47236 KB	Output is correct
13	Correct	376 ms	47272 KB	Output is correct
14	Correct	400 ms	49260 KB	Output is correct
15	Correct	437 ms	51160 KB	Output is correct
16	Correct	436 ms	51004 KB	Output is correct
17	Correct	420 ms	51344 KB	Output is correct
18	Correct	418 ms	51164 KB	Output is correct
19	Correct	418 ms	51156 KB	Output is correct
20	Correct	369 ms	53576 KB	Output is correct
21	Correct	378 ms	52840 KB	Output is correct
22	Correct	418 ms	53104 KB	Output is correct
23	Correct	414 ms	53140 KB	Output is correct
24	Correct	437 ms	53016 KB	Output is correct
25	Correct	423 ms	53196 KB	Output is correct
26	Correct	428 ms	53140 KB	Output is correct
27	Correct	435 ms	53452 KB	Output is correct
28	Correct	411 ms	52692 KB	Output is correct
29	Correct	378 ms	48732 KB	Output is correct
30	Correct	387 ms	50664 KB	Output is correct

Subtask #5
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	429 ms	54924 KB	Output is correct
2	Correct	413 ms	55232 KB	Output is correct
3	Correct	434 ms	55308 KB	Output is correct
4	Correct	457 ms	51176 KB	Output is correct
5	Correct	437 ms	54876 KB	Output is correct
6	Correct	440 ms	52508 KB	Output is correct
7	Correct	440 ms	52396 KB	Output is correct
8	Correct	444 ms	53068 KB	Output is correct
9	Correct	436 ms	52752 KB	Output is correct
10	Correct	442 ms	51260 KB	Output is correct
11	Correct	443 ms	51276 KB	Output is correct
12	Correct	448 ms	47256 KB	Output is correct
13	Correct	442 ms	47188 KB	Output is correct
14	Correct	465 ms	49232 KB	Output is correct
15	Correct	505 ms	51072 KB	Output is correct
16	Correct	485 ms	51128 KB	Output is correct
17	Correct	446 ms	51156 KB	Output is correct
18	Correct	451 ms	51100 KB	Output is correct
19	Correct	418 ms	51136 KB	Output is correct
20	Correct	377 ms	53656 KB	Output is correct
21	Correct	368 ms	52868 KB	Output is correct
22	Correct	422 ms	52960 KB	Output is correct
23	Correct	445 ms	52784 KB	Output is correct
24	Correct	439 ms	52892 KB	Output is correct
25	Correct	427 ms	53048 KB	Output is correct
26	Correct	424 ms	52496 KB	Output is correct
27	Correct	422 ms	53560 KB	Output is correct
28	Correct	421 ms	53772 KB	Output is correct
29	Correct	383 ms	49224 KB	Output is correct
30	Correct	392 ms	50972 KB	Output is correct
31	Correct	8 ms	6424 KB	Output is correct
32	Correct	8 ms	6680 KB	Output is correct
33	Correct	12 ms	7200 KB	Output is correct
34	Correct	7 ms	6420 KB	Output is correct
35	Correct	6 ms	6148 KB	Output is correct
36	Correct	4 ms	6156 KB	Output is correct
37	Correct	4 ms	6160 KB	Output is correct
38	Correct	4 ms	6160 KB	Output is correct
39	Correct	4 ms	6164 KB	Output is correct
40	Correct	5 ms	6164 KB	Output is correct
41	Correct	5 ms	6156 KB	Output is correct
42	Correct	4 ms	6160 KB	Output is correct

Submission #565870

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 55.0 / 55.0

Subtask #5 17.0 / 17.0

Subtask #1
8.0 / 8.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
55.0 / 55.0

Subtask #5
17.0 / 17.0