oj.uz

Submission #102739

# Submission time Handle Problem Language Result Execution time Memory
102739 2019-03-27T11:19:59 Z Minnakhmetov Amusement Park (JOI17_amusement_park) C++14
100 / 100
 640 ms 258336 KB 
#include "Joi.h"

#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

static const int N = 1e4 + 5, D = 60;
static vector<int> g[N];
static int num[N];

static struct Tree {
	vector<int> t[D];
	int id_to_node[D];
	map<int, int> node_to_id;

	Tree() {
		fill(id_to_node, id_to_node + D, -1);
	}

	void addNode(int node) {
		for (int i = 0; i < D; i++) {
			if (id_to_node[i] == -1) {
				id_to_node[i] = node;
				node_to_id[node] = i;
				break;
			}
		}
	}
	void addEdge(int x, int y) {
		x = node_to_id[x];
		y = node_to_id[y];
		t[x].push_back(y);
		t[y].push_back(x);
	}

	void delNode(int id) {
		for (int to : t[id]) {
			t[to].erase(find(all(t[to]), id));
		}
		t[id].clear();
		node_to_id.erase(id_to_node[id]);
		id_to_node[id] = -1;
	}

	int popLeafNotEqualTo(int node) {
		int id = -1;
		for (int i = 0; i < D; i++) {
			if (id_to_node[i] != -1 &&
				id_to_node[i] != node &&
				t[i].size() == 1) {
				id = i;
				break;
			}
		}
		int deletedNode = id_to_node[id];
		delNode(id);
		return deletedNode;
	}

	int getNodeCount() {
		return node_to_id.size();
	}

} tr[N];

static void dfs(int node, int anc, Tree &t) {
	num[node] = t.getNodeCount();
	t.addNode(node);
	if (anc != -1)
		t.addEdge(node, anc);
	if (t.getNodeCount() == 60)
		return;
	for (int to : g[node]) {
		if (num[to] == -1) {
			dfs(to, node, t);
			if (t.getNodeCount() == 60)
				return;
		}
	}
}

static void deep(int node, int anc, Tree t) {
	num[node] = num[t.popLeafNotEqualTo(anc)];
	t.addNode(node);
	t.addEdge(node, anc);
	tr[node] = t;

	for (int to : g[node]) {
		if (num[to] == -1) {
			deep(to, node, t);
		}
	}
}

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]);
	}

	fill(num, num + n, -1);

	Tree fir;
	dfs(0, -1, fir);

	for (int i = 0; i < n; i++) {
		if (num[i] != -1)
			tr[i] = fir;
	}

	for (int i = 0; i < n; i++) {
		if (num[i] != -1) {
			for (int to : g[i]) {
				if (num[to] == -1) {
					deep(to, i, fir);
				}
			}
		}
	}
	
	for(int i = 0; i < n; i++){
		MessageBoard(i, (x >> num[i]) & 1);
	}
}

#include "Ioi.h"

#include <vector>
#include <map>
#include <algorithm>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

static const int N = 1e4 + 5, D = 60;
static vector<int> g[N];
static int num[N];

struct Tree {
	vector<int> t[D];
	int id_to_node[D];
	map<int, int> node_to_id;

	Tree() {
		fill(id_to_node, id_to_node + D, -1);
	}

	void addNode(int node) {
		for (int i = 0; i < D; i++) {
			if (id_to_node[i] == -1) {
				id_to_node[i] = node;
				node_to_id[node] = i;
				break;
			}
		}
	}
	void addEdge(int x, int y) {
		x = node_to_id[x];
		y = node_to_id[y];
		t[x].push_back(y);
		t[y].push_back(x);
	}

	void delNode(int id) {
		for (int to : t[id]) {
			t[to].erase(find(all(t[to]), id));
		}
		t[id].clear();
		node_to_id.erase(id_to_node[id]);
		id_to_node[id] = -1;
	}

	int popLeafNotEqualTo(int node) {
		int id = -1;
		for (int i = 0; i < D; i++) {
			if (id_to_node[i] != -1 &&
				id_to_node[i] != node &&
				t[i].size() == 1) {
				id = i;
				break;
			}
		}
		int deletedNode = id_to_node[id];
		delNode(id);
		return deletedNode;
	}

	int getNodeCount() {
		return node_to_id.size();
	}

} tr[N];

void dfs(int node, int anc, Tree &t) {
	num[node] = t.getNodeCount();
	t.addNode(node);
	if (anc != -1)
		t.addEdge(node, anc);
	if (t.getNodeCount() == 60)
		return;
	for (int to : g[node]) {
		if (num[to] == -1) {
			dfs(to, node, t);
			if (t.getNodeCount() == 60)
				return;
		}
	}
}

void deep(int node, int anc, Tree t) {
	num[node] = num[t.popLeafNotEqualTo(anc)];
	t.addNode(node);
	t.addEdge(node, anc);
	tr[node] = t;

	for (int to : g[node]) {
		if (num[to] == -1) {
			deep(to, node, t);
		}
	}
}

ll ans = 0;
static bool used[D];

void walk(int node, int anc, Tree &t) {
	used[node] = 1;
	for (int to : t.t[node]) {
		if (!used[to]) {
			ans |= (ll)Move(t.id_to_node[to]) << num[t.id_to_node[to]];
			walk(to, node, t);
		}
	}
	if (anc != -1)
		Move(t.id_to_node[anc]);
}

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]);
	}

	fill(num, num + n, -1);

	Tree fir;
	dfs(0, -1, fir);

	for (int i = 0; i < n; i++) {
		if (num[i] != -1)
			tr[i] = fir;
	}

	for (int i = 0; i < n; i++) {
		if (num[i] != -1) {
			for (int to : g[i]) {
				if (num[to] == -1) {
					deep(to, i, fir);
				}
			}
		}
	}

	ans |= (ll)V << num[P];

	walk(tr[P].node_to_id[P], -1, tr[P]);

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 35848 KB Output is correct
2 Correct 45 ms 36500 KB Output is correct
3 Correct 52 ms 37896 KB Output is correct
4 Correct 44 ms 36484 KB Output is correct
5 Correct 45 ms 36612 KB Output is correct
6 Correct 50 ms 36740 KB Output is correct
7 Correct 61 ms 38620 KB Output is correct
8 Correct 47 ms 37888 KB Output is correct
9 Correct 50 ms 37768 KB Output is correct
10 Correct 44 ms 36476 KB Output is correct
11 Correct 56 ms 37672 KB Output is correct
12 Correct 40 ms 35708 KB Output is correct
13 Correct 49 ms 38064 KB Output is correct
14 Correct 52 ms 37896 KB Output is correct
15 Correct 48 ms 38024 KB Output is correct
16 Correct 54 ms 37896 KB Output is correct
17 Correct 53 ms 38108 KB Output is correct
18 Correct 48 ms 38072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 190776 KB Output is correct
2 Correct 515 ms 191880 KB Output is correct
3 Correct 621 ms 192576 KB Output is correct
4 Correct 445 ms 131028 KB Output is correct
5 Correct 550 ms 188656 KB Output is correct
6 Correct 494 ms 164520 KB Output is correct
7 Correct 484 ms 159132 KB Output is correct
8 Correct 480 ms 162512 KB Output is correct
9 Correct 455 ms 154648 KB Output is correct
10 Correct 448 ms 134660 KB Output is correct
11 Correct 468 ms 135076 KB Output is correct
12 Correct 352 ms 122100 KB Output is correct
13 Correct 360 ms 122404 KB Output is correct
14 Correct 405 ms 126436 KB Output is correct
15 Correct 448 ms 131080 KB Output is correct
16 Correct 415 ms 130952 KB Output is correct
17 Correct 397 ms 130876 KB Output is correct
18 Correct 421 ms 130964 KB Output is correct
19 Correct 401 ms 131232 KB Output is correct
20 Correct 475 ms 195952 KB Output is correct
21 Correct 462 ms 193696 KB Output is correct
22 Correct 540 ms 151828 KB Output is correct
23 Correct 466 ms 150148 KB Output is correct
24 Correct 502 ms 151048 KB Output is correct
25 Correct 508 ms 160300 KB Output is correct
26 Correct 449 ms 150152 KB Output is correct
27 Correct 481 ms 150304 KB Output is correct
28 Correct 514 ms 165816 KB Output is correct
29 Correct 425 ms 151052 KB Output is correct
30 Correct 464 ms 144652 KB Output is correct
31 Correct 40 ms 36732 KB Output is correct
32 Correct 46 ms 36968 KB Output is correct
33 Correct 48 ms 37884 KB Output is correct
34 Correct 43 ms 36616 KB Output is correct
35 Correct 51 ms 36464 KB Output is correct
36 Correct 41 ms 35964 KB Output is correct
37 Correct 39 ms 35980 KB Output is correct
38 Correct 44 ms 35716 KB Output is correct
39 Correct 38 ms 35716 KB Output is correct
40 Correct 41 ms 36100 KB Output is correct
41 Correct 41 ms 36724 KB Output is correct
42 Correct 40 ms 35836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36348 KB Output is correct
2 Correct 40 ms 36480 KB Output is correct
3 Correct 44 ms 36460 KB Output is correct
4 Correct 149 ms 70700 KB Output is correct
5 Correct 124 ms 70828 KB Output is correct
6 Correct 128 ms 70704 KB Output is correct
7 Correct 152 ms 70780 KB Output is correct
8 Correct 131 ms 70764 KB Output is correct
9 Correct 590 ms 258336 KB Output is correct
10 Correct 573 ms 258252 KB Output is correct
11 Correct 630 ms 258264 KB Output is correct
12 Correct 43 ms 35724 KB Output is correct
13 Correct 40 ms 35928 KB Output is correct
14 Correct 39 ms 35680 KB Output is correct
15 Correct 41 ms 35708 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 190128 KB Output is correct
2 Correct 640 ms 190340 KB Output is correct
3 Correct 532 ms 191968 KB Output is correct
4 Correct 422 ms 131128 KB Output is correct
5 Correct 575 ms 202472 KB Output is correct
6 Correct 434 ms 156592 KB Output is correct
7 Correct 436 ms 165996 KB Output is correct
8 Correct 433 ms 153992 KB Output is correct
9 Correct 484 ms 143180 KB Output is correct
10 Correct 493 ms 134952 KB Output is correct
11 Correct 552 ms 134640 KB Output is correct
12 Correct 444 ms 122312 KB Output is correct
13 Correct 370 ms 122120 KB Output is correct
14 Correct 392 ms 126496 KB Output is correct
15 Correct 411 ms 130736 KB Output is correct
16 Correct 442 ms 131068 KB Output is correct
17 Correct 445 ms 131328 KB Output is correct
18 Correct 420 ms 131032 KB Output is correct
19 Correct 428 ms 131160 KB Output is correct
20 Correct 525 ms 195916 KB Output is correct
21 Correct 565 ms 193520 KB Output is correct
22 Correct 455 ms 150288 KB Output is correct
23 Correct 493 ms 157904 KB Output is correct
24 Correct 505 ms 157588 KB Output is correct
25 Correct 548 ms 163920 KB Output is correct
26 Correct 514 ms 162240 KB Output is correct
27 Correct 585 ms 169364 KB Output is correct
28 Correct 456 ms 152992 KB Output is correct
29 Correct 447 ms 140616 KB Output is correct
30 Correct 433 ms 156256 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 191036 KB Output is correct
2 Correct 540 ms 190576 KB Output is correct
3 Correct 502 ms 191020 KB Output is correct
4 Correct 423 ms 131224 KB Output is correct
5 Correct 582 ms 227356 KB Output is correct
6 Correct 471 ms 142880 KB Output is correct
7 Correct 438 ms 142684 KB Output is correct
8 Correct 495 ms 153888 KB Output is correct
9 Correct 431 ms 143408 KB Output is correct
10 Correct 466 ms 134576 KB Output is correct
11 Correct 512 ms 134188 KB Output is correct
12 Correct 377 ms 122176 KB Output is correct
13 Correct 438 ms 122272 KB Output is correct
14 Correct 398 ms 126676 KB Output is correct
15 Correct 402 ms 130976 KB Output is correct
16 Correct 417 ms 130988 KB Output is correct
17 Correct 415 ms 131396 KB Output is correct
18 Correct 432 ms 130852 KB Output is correct
19 Correct 452 ms 131568 KB Output is correct
20 Correct 527 ms 195920 KB Output is correct
21 Correct 498 ms 193440 KB Output is correct
22 Correct 456 ms 159772 KB Output is correct
23 Correct 443 ms 150432 KB Output is correct
24 Correct 497 ms 151200 KB Output is correct
25 Correct 487 ms 151344 KB Output is correct
26 Correct 479 ms 151052 KB Output is correct
27 Correct 558 ms 169840 KB Output is correct
28 Correct 513 ms 170524 KB Output is correct
29 Correct 450 ms 157936 KB Output is correct
30 Correct 507 ms 159144 KB Output is correct
31 Correct 43 ms 36484 KB Output is correct
32 Correct 45 ms 36740 KB Output is correct
33 Correct 56 ms 38004 KB Output is correct
34 Correct 43 ms 36612 KB Output is correct
35 Correct 41 ms 36276 KB Output is correct
36 Correct 40 ms 35964 KB Output is correct
37 Correct 35 ms 35836 KB Output is correct
38 Correct 40 ms 35568 KB Output is correct
39 Correct 40 ms 35824 KB Output is correct
40 Correct 44 ms 36228 KB Output is correct
41 Correct 46 ms 36648 KB Output is correct
42 Correct 43 ms 35708 KB Output is correct