Submission #205795

#	Time	Username	Problem	Language	Result	Execution time	Memory
205795		ArshiaDadras	Amusement Park (JOI17_amusement_park)	C++17	45 / 100	55 ms	7420 KiB

Joi

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

const int N = 1e4 + 5, LG = 60;
int n, m, k, a[N], b[N], root[N], h[N], sz[N], par[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]) {
			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]]++;
	for (auto v: adj[u])
		if (k + sz[root[u]] < LG)
			go(v);
}

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

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

bool make_root(int u) {
	memset(root, -1, sizeof root);
	memset(id, -1, sizeof id);
	mark.reset(), dfs_tree(u);
	return build(u);
}
void build_tree() {
	if (!make_root(0))
		for (int u = 0; u < n; u++)
			if (~root[u] && !~root[par[u]]) {
				make_root(u);
				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, LG = 60;
int n, m, k, a[N], b[N], root[N], h[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]] < LG)
			go(v), path[root[u]].push_back(u);
}

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

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

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

void build_tree() {
	if (!make_root(0))
		for (int u = 0; u < n; u++)
			if (~root[u] && !~root[par[u]]) {
				make_root(u);
				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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 55
• Subtask 5: 17 / 17