Submission #514823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
514823	2022-01-18T14:19:28 Z	amunduzbaev	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	80 ms	5840 KB

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

const int N = 1e4 + 5;
vector<int> G[N], tt, ee[N];
int used[N], in[N], cnt = 1;
bitset<60> gg[60], uu;

void dfs(int u){
	used[u] = 1;
	for(auto x : G[u]){
		if(used[x]) continue;
		ee[u].push_back(x);
		ee[x].push_back(u);
		if((int)tt.size() < 60){
			in[x] = tt.size();
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
			tt.push_back(x);
			dfs(x); continue;
		}
		int par = -1;
		bitset<60> tmp;
		for(int i=0;i<60;i++){
			if(i == in[u]) continue;
			int cc = 0;
			for(int j=0;j<60;j++) cc += gg[i][j];
			if(cc != 1) continue;
			
			tmp = gg[i], par = tt[i];
			for(int j=0;j<60;j++) gg[i][j] = gg[j][i] = 0;
			tt[i] = x;
			gg[in[u]][i] = gg[i][in[u]] = 1;
			in[x] = i;
			break;
		}
		dfs(x);
		
		//~ assert(~par);
		for(int j=0;j<60;j++){
			gg[in[par]][j] = gg[j][in[par]] = tmp[j];
		} tt[in[par]] = par;
	}
}

void Joi(int n, int m, int a[], int b[], long long x, int t){
	for(int i=0;i<m;i++){
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	} for(int i=0;i<n;i++){
		sort(G[i].begin(), G[i].end());
	}
	
	tt.push_back(0);
	memset(in, -1, sizeof in);
	in[0] = 0; dfs(0);
	
	//~ for(int i=0;i<n;i++) cout<<in[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<n;i++){
		assert(~in[i]);
		MessageBoard(i, x >> in[i] & 1);
	}
}

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

const int N = 1e4 + 5;
vector<int> G[N], tt, ee[N];
int used[N], in[N], cnt = 1;
bitset<60> gg[60], uu;

void dfs(int u){
	used[u] = 1;
	for(auto x : G[u]){
		if(used[x]) continue;
		ee[u].push_back(x);
		ee[x].push_back(u);
		if((int)tt.size() < 60){
			in[x] = tt.size();
			gg[in[u]][in[x]] = gg[in[x]][in[u]] = 1;
			tt.push_back(x);
			dfs(x); continue;
		}
		int par = -1;
		bitset<60> tmp;
		for(int i=0;i<60;i++){
			if(i == in[u]) continue;
			int cc = 0;
			for(int j=0;j<60;j++) cc += gg[i][j];
			if(cc != 1) continue;
			
			tmp = gg[i], par = tt[i];
			for(int j=0;j<60;j++) gg[i][j] = gg[j][i] = 0;
			tt[i] = x;
			gg[in[u]][i] = gg[i][in[u]] = 1;
			in[x] = i;
			break;
		}
		dfs(x);
		
		//~ assert(~par);
		for(int j=0;j<60;j++){
			gg[in[par]][j] = gg[j][in[par]] = tmp[j];
		} tt[in[par]] = par;
	}
}

long long Ioi(int n, int m, int a[], int b[], int p, int v, int t){
	for(int i=0;i<m;i++){
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
	} for(int i=0;i<n;i++){
		sort(G[i].begin(), G[i].end());
	}
	
	tt.push_back(0);
	memset(in, -1, sizeof in);
	in[0] = 0; dfs(0);
	
	//~ for(int i=0;i<n;i++) cout<<in[i]<<" ";
	//~ cout<<"\n";
	
	memset(used, 0, sizeof used);
	long long x = 0;
	function<void(int)> go = [&](int u){
		used[u] = uu[in[u]] = 1;
		if(v) x |= (1ll << in[u]);
		for(auto x : ee[u]){
			if(used[x] || uu[in[x]]) continue;
			v = Move(x), go(x),
			v = Move(u);
		}
	};
	go(p);
	for(int i=0;i<60;i++) assert(uu[i]);
	
	return x;
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1648 KB	Output is correct
2	Correct	2 ms	1648 KB	Output is correct
3	Correct	2 ms	1772 KB	Output is correct
4	Correct	1 ms	1640 KB	Output is correct
5	Correct	2 ms	1640 KB	Output is correct
6	Correct	2 ms	1768 KB	Output is correct
7	Correct	2 ms	1772 KB	Output is correct
8	Correct	2 ms	1724 KB	Output is correct
9	Correct	2 ms	1668 KB	Output is correct
10	Correct	1 ms	1648 KB	Output is correct
11	Correct	5 ms	2044 KB	Output is correct
12	Correct	1 ms	1648 KB	Output is correct
13	Correct	2 ms	1704 KB	Output is correct
14	Correct	3 ms	1704 KB	Output is correct
15	Correct	2 ms	1784 KB	Output is correct
16	Correct	2 ms	1776 KB	Output is correct
17	Correct	2 ms	1712 KB	Output is correct
18	Correct	2 ms	1784 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	5424 KB	Output is correct
2	Correct	67 ms	5836 KB	Output is correct
3	Correct	72 ms	5828 KB	Output is correct
4	Correct	34 ms	3904 KB	Output is correct
5	Correct	55 ms	4704 KB	Output is correct
6	Correct	69 ms	4408 KB	Output is correct
7	Correct	54 ms	4472 KB	Output is correct
8	Correct	53 ms	4556 KB	Output is correct
9	Correct	64 ms	4604 KB	Output is correct
10	Correct	23 ms	3996 KB	Output is correct
11	Correct	20 ms	4160 KB	Output is correct
12	Correct	35 ms	3616 KB	Output is correct
13	Correct	39 ms	3704 KB	Output is correct
14	Correct	40 ms	3812 KB	Output is correct
15	Correct	27 ms	3848 KB	Output is correct
16	Correct	32 ms	3868 KB	Output is correct
17	Correct	33 ms	3888 KB	Output is correct
18	Correct	37 ms	3848 KB	Output is correct
19	Correct	40 ms	3884 KB	Output is correct
20	Correct	60 ms	4756 KB	Output is correct
21	Correct	53 ms	4800 KB	Output is correct
22	Correct	59 ms	4284 KB	Output is correct
23	Correct	56 ms	4480 KB	Output is correct
24	Correct	59 ms	4352 KB	Output is correct
25	Correct	56 ms	4432 KB	Output is correct
26	Correct	54 ms	4572 KB	Output is correct
27	Correct	55 ms	4568 KB	Output is correct
28	Correct	57 ms	4684 KB	Output is correct
29	Correct	50 ms	4272 KB	Output is correct
30	Correct	57 ms	4384 KB	Output is correct
31	Correct	2 ms	1652 KB	Output is correct
32	Correct	2 ms	1644 KB	Output is correct
33	Correct	2 ms	1776 KB	Output is correct
34	Correct	2 ms	1652 KB	Output is correct
35	Correct	2 ms	1756 KB	Output is correct
36	Correct	2 ms	1652 KB	Output is correct
37	Correct	2 ms	1644 KB	Output is correct
38	Correct	2 ms	1652 KB	Output is correct
39	Correct	2 ms	1652 KB	Output is correct
40	Correct	2 ms	1656 KB	Output is correct
41	Correct	2 ms	1648 KB	Output is correct
42	Correct	2 ms	1644 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	1652 KB	Output is correct
2	Correct	1 ms	1640 KB	Output is correct
3	Correct	2 ms	1740 KB	Output is correct
4	Correct	9 ms	2348 KB	Output is correct
5	Correct	10 ms	2308 KB	Output is correct
6	Correct	9 ms	2328 KB	Output is correct
7	Correct	10 ms	2308 KB	Output is correct
8	Correct	10 ms	2308 KB	Output is correct
9	Correct	55 ms	5528 KB	Output is correct
10	Correct	51 ms	5480 KB	Output is correct
11	Correct	56 ms	5436 KB	Output is correct
12	Correct	2 ms	1640 KB	Output is correct
13	Correct	2 ms	1644 KB	Output is correct
14	Correct	1 ms	1648 KB	Output is correct
15	Correct	2 ms	1640 KB	Output is correct

Subtask #4
55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	5484 KB	Output is correct
2	Correct	65 ms	5532 KB	Output is correct
3	Correct	64 ms	5352 KB	Output is correct
4	Correct	33 ms	4036 KB	Output is correct
5	Correct	62 ms	5292 KB	Output is correct
6	Correct	68 ms	4684 KB	Output is correct
7	Correct	55 ms	4664 KB	Output is correct
8	Correct	54 ms	4196 KB	Output is correct
9	Correct	61 ms	4248 KB	Output is correct
10	Correct	22 ms	4116 KB	Output is correct
11	Correct	24 ms	4112 KB	Output is correct
12	Correct	49 ms	3704 KB	Output is correct
13	Correct	39 ms	3560 KB	Output is correct
14	Correct	38 ms	3712 KB	Output is correct
15	Correct	27 ms	3844 KB	Output is correct
16	Correct	34 ms	3824 KB	Output is correct
17	Correct	34 ms	3888 KB	Output is correct
18	Correct	31 ms	3840 KB	Output is correct
19	Correct	41 ms	3940 KB	Output is correct
20	Correct	56 ms	4744 KB	Output is correct
21	Correct	55 ms	4792 KB	Output is correct
22	Correct	57 ms	4580 KB	Output is correct
23	Correct	55 ms	4340 KB	Output is correct
24	Correct	57 ms	4480 KB	Output is correct
25	Correct	73 ms	4668 KB	Output is correct
26	Correct	56 ms	4712 KB	Output is correct
27	Correct	64 ms	4736 KB	Output is correct
28	Correct	56 ms	4356 KB	Output is correct
29	Correct	50 ms	4256 KB	Output is correct
30	Correct	55 ms	4284 KB	Output is correct

Subtask #5
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	5388 KB	Output is correct
2	Correct	66 ms	5448 KB	Output is correct
3	Correct	65 ms	5840 KB	Output is correct
4	Correct	34 ms	3864 KB	Output is correct
5	Correct	57 ms	5380 KB	Output is correct
6	Correct	80 ms	4392 KB	Output is correct
7	Correct	58 ms	4348 KB	Output is correct
8	Correct	56 ms	4584 KB	Output is correct
9	Correct	56 ms	4360 KB	Output is correct
10	Correct	22 ms	4068 KB	Output is correct
11	Correct	22 ms	4032 KB	Output is correct
12	Correct	42 ms	3508 KB	Output is correct
13	Correct	41 ms	3776 KB	Output is correct
14	Correct	40 ms	3784 KB	Output is correct
15	Correct	37 ms	3820 KB	Output is correct
16	Correct	30 ms	3860 KB	Output is correct
17	Correct	36 ms	3840 KB	Output is correct
18	Correct	39 ms	3964 KB	Output is correct
19	Correct	48 ms	3852 KB	Output is correct
20	Correct	54 ms	4844 KB	Output is correct
21	Correct	54 ms	4920 KB	Output is correct
22	Correct	63 ms	4420 KB	Output is correct
23	Correct	57 ms	4404 KB	Output is correct
24	Correct	55 ms	4468 KB	Output is correct
25	Correct	60 ms	4356 KB	Output is correct
26	Correct	56 ms	4372 KB	Output is correct
27	Correct	57 ms	4580 KB	Output is correct
28	Correct	56 ms	4708 KB	Output is correct
29	Correct	53 ms	4528 KB	Output is correct
30	Correct	56 ms	4504 KB	Output is correct
31	Correct	2 ms	1652 KB	Output is correct
32	Correct	2 ms	1652 KB	Output is correct
33	Correct	2 ms	1788 KB	Output is correct
34	Correct	2 ms	1644 KB	Output is correct
35	Correct	2 ms	1644 KB	Output is correct
36	Correct	2 ms	1648 KB	Output is correct
37	Correct	2 ms	1652 KB	Output is correct
38	Correct	2 ms	1720 KB	Output is correct
39	Correct	2 ms	1644 KB	Output is correct
40	Correct	2 ms	1656 KB	Output is correct
41	Correct	2 ms	1652 KB	Output is correct
42	Correct	2 ms	1644 KB	Output is correct

Submission #514823

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