답안 #205695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205695	2020-02-29T13:49:30 Z	ArshiaDadras	Amusement Park (JOI17_amusement_park)	C++14	45 / 100	46 ms	7216 KB

Joi

/* In the name of Allah */
#include<bits/stdc++.h>
#include<Joi.h>
using namespace std;

const int N = 1e4 + 5;
int n, m, k, a[N], b[N], root[N], down[N], sz[N], id[N];
vector<int> ed[N], adj[N];
bitset<N> mark;

void dfs_tree(int u) {
	mark.set(u);
	vector<int> help;
	for (auto v: ed[u])
		if (!mark[v]) {
			dfs_tree(v);
			help.push_back(v);
		}
	adj[u] = help;
}

void change(int u) {
	for (auto v: adj[u])
		if (!~root[v]) {
			root[v] = root[u];
			change(v);
		}
}

void go(int u) {
	id[u] = sz[root[u]]++;
	for (auto v: adj[u])
		if (k + sz[root[u]] < 60)
			go(v);
}

void go_big(int u) {
	for (sz[u] = 0; !adj[u].empty(); u = adj[u][0]) {
		k = sz[adj[u][0]], id[u] = sz[root[u]]++;
		for (auto v: adj[u])
			if (k + sz[root[u]] < 60 && v ^ adj[u][0])
				go(v);
	}
	id[u] = sz[root[u]]++;
}

bool build(int u) {
	vector<int> help;
	sz[u] = 1, down[u] = 0;
	for (auto v: adj[u])
		if (!build(v)) {
			sz[u] += sz[v];
			help.push_back(v);
			down[u] = max(down[u], down[v] + 1);
		}
	sort(help.begin(), help.end(), [] (int u, int v) {
		return down[u] > down[v];
	});
	adj[u] = help;
	if (sz[u] < 60)
		return false;
	change(root[u] = u);
	return go_big(u), true;
}

bool set_root(int v) {
	for (int u = 0; u < n; u++)
		id[u] = root[u] = -1;
	mark.reset(), dfs_tree(v);
	return build(v);
}

void build_tree() {
	if (!set_root(0))
		for (int i = 0; i < m; i++) {
			if (~root[a[i]])
				swap(a[i], b[i]);
			if (!~root[a[i]] && ~root[b[i]]) {
				set_root(b[i]);
				break;
			}
		}
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	n = N, m = M;
	for (int u = 0; u < n; u++)
		ed[u].clear();
	for (int i = 0; i < m; i++) {
		ed[a[i] = A[i]].push_back(B[i]);
		ed[b[i] = B[i]].push_back(A[i]);
	}
	build_tree();
	for (int u = 0; u < n; u++)
		MessageBoard(u, ~id[u]? X >> id[u] & 1: 0);
}

Ioi

/* In the name of Allah */
#include<bits/stdc++.h>
#include<Ioi.h>
using namespace std;

const int N = 1e4 + 5;
int n, m, k, a[N], b[N], root[N], down[N], sz[N], par[N], id[N];
vector<int> ed[N], adj[N], path[N];
bitset<N> mark;

void dfs_tree(int u) {
	mark.set(u);
	vector<int> help;
	for (auto v: ed[u])
		if (!mark[v]) {
			help.push_back(v);
			dfs_tree(v), par[v] = u;
		}
	adj[u] = help;
}

void change(int u) {
	for (auto v: adj[u])
		if (!~root[v]) {
			root[v] = root[u];
			change(v);
		}
}

void go(int u) {
	id[u] = sz[root[u]]++;
	path[root[u]].push_back(u);
	for (auto v: adj[u])
		if (k + sz[root[u]] < 60)
			go(v), path[root[u]].push_back(u);
}

void go_big(int u) {
	for (sz[u] = 0; !adj[u].empty(); u = adj[u][0]) {
		path[root[u]].push_back(u);
		k = sz[adj[u][0]], id[u] = sz[root[u]]++;
		for (auto v: adj[u])
			if (k + sz[root[u]] < 60 && v ^ adj[u][0])
				go(v), path[root[u]].push_back(u);
	}
	id[u] = sz[root[u]]++;
	path[root[u]].push_back(u);
}

bool build(int u) {
	vector<int> help;
	sz[u] = 1, down[u] = 0;
	for (auto v: adj[u])
		if (!build(v)) {
			sz[u] += sz[v];
			help.push_back(v);
			down[u] = max(down[u], down[v] + 1);
		}
	sort(help.begin(), help.end(), [] (int u, int v) {
		return down[u] > down[v];
	});
	adj[u] = help;
	if (sz[u] < 60)
		return false;
	change(root[u] = u);
	return go_big(u), true;
}

bool set_root(int v) {
	for (int u = 0; u < n; u++) {
		id[u] = root[u] = -1;
		path[u].clear();
	}
	mark.reset(), dfs_tree(v);
	return build(v);
}

void build_tree() {
	if (!set_root(0))
		for (int i = 0; i < m; i++) {
			if (~root[a[i]])
				swap(a[i], b[i]);
			if (!~root[a[i]] && ~root[b[i]]) {
				set_root(b[i]);
				break;
			}
		}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	n = N, m = M;
	for (int u = 0; u < n; u++)
		ed[u].clear();
	for (int i = 0; i < m; i++) {
		ed[a[i] = A[i]].push_back(B[i]);
		ed[b[i] = B[i]].push_back(A[i]);
	}
	build_tree();
	while (P ^ root[P])
		V = Move(P = par[P]);
	long long answer = V;
	for (auto u: path[P]) {
		if (P ^ u)
			V = Move(P = u);
		answer |= 1LL * V << id[P];
	}
	return answer;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	2292 KB	Output is correct
2	Correct	10 ms	2252 KB	Output is correct
3	Correct	10 ms	2116 KB	Output is correct
4	Correct	10 ms	2124 KB	Output is correct
5	Correct	10 ms	2164 KB	Output is correct
6	Correct	10 ms	2164 KB	Output is correct
7	Correct	10 ms	2264 KB	Output is correct
8	Correct	10 ms	2052 KB	Output is correct
9	Correct	10 ms	2172 KB	Output is correct
10	Correct	10 ms	2024 KB	Output is correct
11	Correct	15 ms	2260 KB	Output is correct
12	Correct	10 ms	2036 KB	Output is correct
13	Correct	10 ms	2044 KB	Output is correct
14	Correct	10 ms	2272 KB	Output is correct
15	Correct	10 ms	2272 KB	Output is correct
16	Correct	11 ms	2136 KB	Output is correct
17	Correct	10 ms	2044 KB	Output is correct
18	Correct	11 ms	2172 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	5504 KB	Output is correct
2	Correct	43 ms	5460 KB	Output is correct
3	Correct	43 ms	5460 KB	Output is correct
4	Correct	33 ms	4364 KB	Output is correct
5	Correct	39 ms	5780 KB	Output is correct
6	Correct	36 ms	5240 KB	Output is correct
7	Correct	36 ms	5216 KB	Output is correct
8	Correct	30 ms	5416 KB	Output is correct
9	Correct	35 ms	5540 KB	Output is correct
10	Correct	27 ms	4284 KB	Output is correct
11	Correct	27 ms	4292 KB	Output is correct
12	Correct	33 ms	4140 KB	Output is correct
13	Correct	32 ms	4172 KB	Output is correct
14	Correct	32 ms	4164 KB	Output is correct
15	Correct	33 ms	4640 KB	Output is correct
16	Correct	33 ms	4636 KB	Output is correct
17	Correct	33 ms	4340 KB	Output is correct
18	Correct	33 ms	4336 KB	Output is correct
19	Correct	33 ms	4468 KB	Output is correct
20	Correct	30 ms	5692 KB	Output is correct
21	Correct	28 ms	5588 KB	Output is correct
22	Correct	35 ms	4956 KB	Output is correct
23	Correct	34 ms	5424 KB	Output is correct
24	Correct	36 ms	5160 KB	Output is correct
25	Correct	33 ms	5052 KB	Output is correct
26	Correct	34 ms	5516 KB	Output is correct
27	Correct	34 ms	5540 KB	Output is correct
28	Correct	30 ms	5384 KB	Output is correct
29	Correct	32 ms	5164 KB	Output is correct
30	Correct	34 ms	5256 KB	Output is correct
31	Correct	10 ms	2276 KB	Output is correct
32	Correct	10 ms	2296 KB	Output is correct
33	Correct	10 ms	2248 KB	Output is correct
34	Correct	10 ms	2276 KB	Output is correct
35	Correct	10 ms	2036 KB	Output is correct
36	Correct	10 ms	2160 KB	Output is correct
37	Correct	10 ms	1912 KB	Output is correct
38	Correct	10 ms	2052 KB	Output is correct
39	Correct	10 ms	2048 KB	Output is correct
40	Correct	10 ms	2288 KB	Output is correct
41	Correct	10 ms	2168 KB	Output is correct
42	Correct	10 ms	1908 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	2164 KB	Output is correct
2	Correct	10 ms	2276 KB	Output is correct
3	Correct	10 ms	2280 KB	Output is correct
4	Correct	13 ms	2860 KB	Output is correct
5	Correct	14 ms	2864 KB	Output is correct
6	Correct	12 ms	3088 KB	Output is correct
7	Correct	14 ms	2856 KB	Output is correct
8	Correct	14 ms	2856 KB	Output is correct
9	Correct	32 ms	6976 KB	Output is correct
10	Correct	30 ms	7216 KB	Output is correct
11	Correct	31 ms	6972 KB	Output is correct
12	Correct	10 ms	1916 KB	Output is correct
13	Correct	10 ms	1932 KB	Output is correct
14	Correct	10 ms	2140 KB	Output is correct
15	Correct	10 ms	2044 KB	Output is correct

Subtask #4

0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	5488 KB	Output is correct
2	Correct	43 ms	5492 KB	Output is correct
3	Incorrect	34 ms	4308 KB	Wrong Answer [7]
4	Halted	0 ms	0 KB	-

Subtask #5

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	5492 KB	Output is correct
2	Correct	46 ms	5508 KB	Output is correct
3	Correct	43 ms	5608 KB	Output is correct
4	Correct	33 ms	4356 KB	Output is correct
5	Correct	31 ms	6380 KB	Output is correct
6	Correct	35 ms	5260 KB	Output is correct
7	Correct	36 ms	4924 KB	Output is correct
8	Correct	34 ms	5536 KB	Output is correct
9	Correct	31 ms	5224 KB	Output is correct
10	Correct	27 ms	4504 KB	Output is correct
11	Correct	27 ms	4528 KB	Output is correct
12	Correct	30 ms	4140 KB	Output is correct
13	Correct	27 ms	4164 KB	Output is correct
14	Correct	33 ms	4276 KB	Output is correct
15	Correct	34 ms	4636 KB	Output is correct
16	Correct	32 ms	4632 KB	Output is correct
17	Correct	33 ms	4324 KB	Output is correct
18	Correct	37 ms	4332 KB	Output is correct
19	Correct	33 ms	4284 KB	Output is correct
20	Correct	28 ms	5720 KB	Output is correct
21	Correct	30 ms	5564 KB	Output is correct
22	Correct	36 ms	5216 KB	Output is correct
23	Correct	31 ms	5148 KB	Output is correct
24	Correct	41 ms	5180 KB	Output is correct
25	Correct	34 ms	5308 KB	Output is correct
26	Correct	34 ms	4952 KB	Output is correct
27	Correct	36 ms	5456 KB	Output is correct
28	Correct	35 ms	5768 KB	Output is correct
29	Correct	31 ms	5404 KB	Output is correct
30	Correct	33 ms	5192 KB	Output is correct
31	Correct	11 ms	2164 KB	Output is correct
32	Correct	10 ms	2248 KB	Output is correct
33	Correct	10 ms	2280 KB	Output is correct
34	Correct	11 ms	2284 KB	Output is correct
35	Correct	10 ms	2292 KB	Output is correct
36	Correct	10 ms	2300 KB	Output is correct
37	Correct	10 ms	2196 KB	Output is correct
38	Correct	12 ms	1912 KB	Output is correct
39	Correct	10 ms	1916 KB	Output is correct
40	Correct	10 ms	2136 KB	Output is correct
41	Correct	11 ms	2272 KB	Output is correct
42	Correct	10 ms	1908 KB	Output is correct