답안 #48580 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48580	2018-05-17T03:12:19 Z	Namnamseo	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	48 ms	24416 KB

#include "Joi.h"

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

static vector<int> edge[10010];
static int ind[10010], nt, hist[20010], dep[10010], par[10010], hn;
static void dfs(int x){
	ind[x] = ++nt;
	hist[hn++] = x;
	for(int y:edge[x]){
		if(ind[y]) continue;
		dep[y]=dep[x]+1;
		par[y]=x;
		dfs(y);
		hist[hn++] = x;
	}
}
static void do_graph(int N, int M, int A[], int B[]){
	for(int i=0; i<M; ++i){
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) sort(edge[i].begin(), edge[i].end());
	nt = 0; hn = 0;
	dep[0]=1;
	dfs(0);
}

static int pick_bit(long long x, int which){
	return 1 & (x >> which);
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	do_graph(N, M, A, B);
	if(*max_element(dep, dep+N) >= 60){
		for(int i = 0; i < N; i++){
			MessageBoard(i, pick_bit(X, (dep[i]-1) % 60));
		}
		return;
	}
	for(int i = 0; i < N; i++){
		MessageBoard(i, pick_bit(X, ind[i] % 60));
	}
}

#include "Ioi.h"

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

static vector<int> edge[10010];
static int ind[10010], nt, hist[20010], dep[10010], par[10010], hn, fh[10010];
static void dfs(int x){
	ind[x] = ++nt;
	fh[x] = hn;
	hist[hn++] = x;
	for(int y:edge[x]){
		if(ind[y]) continue;
		dep[y]=dep[x]+1;
		par[y]=x;
		dfs(y);
		hist[hn++] = x;
	}
}
static void do_graph(int N, int M, int A[], int B[]){
	for(int i=0; i<M; ++i){
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
	}
	for(int i=0; i<N; ++i) sort(edge[i].begin(), edge[i].end());
	nt = 0; hn = 0;
	dep[0]=1;
	dfs(0);
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T){
	do_graph(N, M, A, B);
	if(*max_element(dep, dep+N) >= 60){
		if(dep[P] >= 60){
			long long ret = 0;
			for(int i=0; i<60; ++i){
				if(V) ret |= (1LL << ((dep[P]-1) % 60));
				V = Move(par[P]);
				P = par[P];
			}
			return ret;
		} else {
			while(P != 0){
				V = Move(par[P]);
				P = par[P];
			}
			vector<int> tmp;
			int p = max_element(dep, dep+N) - dep;
			while(true){
				tmp.push_back(p);
				if(p == 0) break;
				p = par[p];
			}
			int n = tmp.size();
			long long ret = 0;
			for(int i=1; i<=60; ++i){
				int p = tmp[n-i];
				if(V) ret |= (1ll << ((dep[p] - 1) % 60));
				if(i < 60){
					V = Move(tmp[n-i-1]);
				}
			}
			return ret;
		}
	}
	int p = fh[P];
	long long mask = 0;
	for(int step=0; step<120; ++step){
		if(p == hn-1) p = 0;
		mask |= (1LL << (ind[hist[p]] % 60));
		++p;
	}
	const long long ALL = ((1LL<<60) - 1);
	if(mask == ALL){
		long long ret = 0, mask = 0;
		int p = fh[P];
		for(int step=0; step<120 || T!=5; ++step){
			if(p == hn-1) p = 0;
			mask |= (1LL << (ind[hist[p]] % 60));
			if(V) ret |= (1LL << (ind[hist[p]] % 60));
			if(mask == ALL) break;
			V = Move(hist[++p]);
		}
		return ret;
	}
	long long ret = 0; mask = 0;
	p = 0;
	for(int i=0; i<hn; ++i) if(hist[i]==P) p=i;
	for(int step=0; step<120 || T!=5; ++step){
		if(p == 0) p = hn-1;
		mask |= (1LL << (ind[hist[p]] % 60));
		if(V) ret |= (1LL << (ind[hist[p]] % 60));
		if(mask == ALL) break;
		V = Move(hist[--p]);
	}
	return ret;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	1388 KB	Output is correct
2	Correct	4 ms	1760 KB	Output is correct
3	Correct	4 ms	1808 KB	Output is correct
4	Correct	4 ms	1912 KB	Output is correct
5	Correct	4 ms	2176 KB	Output is correct
6	Correct	4 ms	2192 KB	Output is correct
7	Correct	4 ms	2192 KB	Output is correct
8	Correct	4 ms	2192 KB	Output is correct
9	Correct	4 ms	2192 KB	Output is correct
10	Correct	4 ms	2192 KB	Output is correct
11	Correct	9 ms	2524 KB	Output is correct
12	Correct	4 ms	2536 KB	Output is correct
13	Correct	4 ms	2536 KB	Output is correct
14	Correct	5 ms	2536 KB	Output is correct
15	Correct	4 ms	2536 KB	Output is correct
16	Correct	4 ms	2536 KB	Output is correct
17	Correct	5 ms	2536 KB	Output is correct
18	Correct	4 ms	2536 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	5536 KB	Output is correct
2	Correct	34 ms	5880 KB	Output is correct
3	Correct	33 ms	6396 KB	Output is correct
4	Correct	20 ms	6608 KB	Output is correct
5	Correct	19 ms	6608 KB	Output is correct
6	Correct	20 ms	6608 KB	Output is correct
7	Correct	23 ms	6608 KB	Output is correct
8	Correct	20 ms	6672 KB	Output is correct
9	Correct	20 ms	6780 KB	Output is correct
10	Correct	19 ms	6824 KB	Output is correct
11	Correct	19 ms	6824 KB	Output is correct
12	Correct	17 ms	6840 KB	Output is correct
13	Correct	17 ms	7040 KB	Output is correct
14	Correct	19 ms	7228 KB	Output is correct
15	Correct	20 ms	7336 KB	Output is correct
16	Correct	19 ms	7560 KB	Output is correct
17	Correct	19 ms	7848 KB	Output is correct
18	Correct	19 ms	8016 KB	Output is correct
19	Correct	19 ms	8128 KB	Output is correct
20	Correct	15 ms	8624 KB	Output is correct
21	Correct	15 ms	9012 KB	Output is correct
22	Correct	26 ms	9112 KB	Output is correct
23	Correct	19 ms	9348 KB	Output is correct
24	Correct	19 ms	9584 KB	Output is correct
25	Correct	19 ms	9604 KB	Output is correct
26	Correct	19 ms	9848 KB	Output is correct
27	Correct	19 ms	10208 KB	Output is correct
28	Correct	19 ms	10400 KB	Output is correct
29	Correct	17 ms	10524 KB	Output is correct
30	Correct	19 ms	10592 KB	Output is correct
31	Correct	4 ms	10592 KB	Output is correct
32	Correct	4 ms	10592 KB	Output is correct
33	Correct	4 ms	10592 KB	Output is correct
34	Correct	4 ms	10592 KB	Output is correct
35	Correct	4 ms	10592 KB	Output is correct
36	Correct	4 ms	10592 KB	Output is correct
37	Correct	4 ms	10592 KB	Output is correct
38	Correct	4 ms	10592 KB	Output is correct
39	Correct	4 ms	10592 KB	Output is correct
40	Correct	4 ms	10592 KB	Output is correct
41	Correct	4 ms	10592 KB	Output is correct
42	Correct	5 ms	10592 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	10592 KB	Output is correct
2	Correct	4 ms	10592 KB	Output is correct
3	Correct	4 ms	10592 KB	Output is correct
4	Correct	7 ms	10592 KB	Output is correct
5	Correct	7 ms	10592 KB	Output is correct
6	Correct	6 ms	10592 KB	Output is correct
7	Correct	7 ms	10592 KB	Output is correct
8	Correct	6 ms	10592 KB	Output is correct
9	Correct	22 ms	11576 KB	Output is correct
10	Correct	22 ms	11960 KB	Output is correct
11	Correct	21 ms	12276 KB	Output is correct
12	Correct	4 ms	12496 KB	Output is correct
13	Correct	4 ms	12496 KB	Output is correct
14	Correct	4 ms	12496 KB	Output is correct
15	Correct	5 ms	12496 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	12712 KB	Output is correct
2	Correct	31 ms	13136 KB	Output is correct
3	Correct	32 ms	13652 KB	Output is correct
4	Correct	19 ms	13960 KB	Output is correct
5	Correct	19 ms	13960 KB	Output is correct
6	Correct	19 ms	13960 KB	Output is correct
7	Correct	19 ms	13960 KB	Output is correct
8	Correct	25 ms	13960 KB	Output is correct
9	Correct	19 ms	13960 KB	Output is correct
10	Correct	26 ms	14104 KB	Output is correct
11	Correct	19 ms	14248 KB	Output is correct
12	Correct	17 ms	14248 KB	Output is correct
13	Correct	19 ms	14268 KB	Output is correct
14	Correct	18 ms	14456 KB	Output is correct
15	Correct	20 ms	14628 KB	Output is correct
16	Correct	19 ms	14796 KB	Output is correct
17	Correct	20 ms	15044 KB	Output is correct
18	Correct	20 ms	15220 KB	Output is correct
19	Correct	19 ms	15388 KB	Output is correct
20	Correct	20 ms	15892 KB	Output is correct
21	Correct	15 ms	16300 KB	Output is correct
22	Correct	19 ms	16424 KB	Output is correct
23	Correct	19 ms	16460 KB	Output is correct
24	Correct	19 ms	16592 KB	Output is correct
25	Correct	26 ms	16836 KB	Output is correct
26	Correct	26 ms	17028 KB	Output is correct
27	Correct	20 ms	17312 KB	Output is correct
28	Correct	19 ms	17552 KB	Output is correct
29	Correct	17 ms	17632 KB	Output is correct
30	Correct	18 ms	17804 KB	Output is correct

Subtask #5
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	48 ms	19192 KB	Output is correct
2	Correct	34 ms	19648 KB	Output is correct
3	Correct	44 ms	19908 KB	Output is correct
4	Correct	26 ms	20104 KB	Output is correct
5	Correct	19 ms	20160 KB	Output is correct
6	Correct	20 ms	20216 KB	Output is correct
7	Correct	20 ms	20216 KB	Output is correct
8	Correct	19 ms	20288 KB	Output is correct
9	Correct	22 ms	20360 KB	Output is correct
10	Correct	19 ms	20376 KB	Output is correct
11	Correct	18 ms	20392 KB	Output is correct
12	Correct	17 ms	20528 KB	Output is correct
13	Correct	17 ms	20656 KB	Output is correct
14	Correct	19 ms	20844 KB	Output is correct
15	Correct	19 ms	21048 KB	Output is correct
16	Correct	19 ms	21248 KB	Output is correct
17	Correct	19 ms	21440 KB	Output is correct
18	Correct	19 ms	21680 KB	Output is correct
19	Correct	20 ms	21904 KB	Output is correct
20	Correct	15 ms	22512 KB	Output is correct
21	Correct	16 ms	22768 KB	Output is correct
22	Correct	19 ms	22824 KB	Output is correct
23	Correct	19 ms	22888 KB	Output is correct
24	Correct	23 ms	23124 KB	Output is correct
25	Correct	20 ms	23316 KB	Output is correct
26	Correct	19 ms	23540 KB	Output is correct
27	Correct	20 ms	23884 KB	Output is correct
28	Correct	19 ms	24100 KB	Output is correct
29	Correct	19 ms	24220 KB	Output is correct
30	Correct	19 ms	24340 KB	Output is correct
31	Correct	4 ms	24416 KB	Output is correct
32	Correct	4 ms	24416 KB	Output is correct
33	Correct	4 ms	24416 KB	Output is correct
34	Correct	4 ms	24416 KB	Output is correct
35	Correct	4 ms	24416 KB	Output is correct
36	Correct	4 ms	24416 KB	Output is correct
37	Correct	4 ms	24416 KB	Output is correct
38	Correct	4 ms	24416 KB	Output is correct
39	Correct	4 ms	24416 KB	Output is correct
40	Correct	4 ms	24416 KB	Output is correct
41	Correct	4 ms	24416 KB	Output is correct
42	Correct	4 ms	24416 KB	Output is correct

답안 #48580

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