oj.uz

Submission #48580

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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