oj.uz

Submission #205648

# Submission time Handle Problem Language Result Execution time Memory
205648 2020-02-29T11:24:01 Z ArshiaDadras Amusement Park (JOI17_amusement_park) C++14
10 / 100
 53 ms 8236 KB 
/* In the name of Allah */
#include<bits/stdc++.h>
#include<Joi.h>
using namespace std;

const int N = 1e4 + 5;
int n, m, 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, int &ted) {
	id[u] = ted++;
	for (auto v: adj[u])
		if (ted < 60)
			go(v, ted);
}

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

void build(int u) {
	vector<int> help;
	sz[u] = 1, down[u] = 0;
	for (auto v: adj[u]) {
		build(v);
		if (!~root[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;
	sz[root[u] = u] = sz[adj[u][id[u] = 0]] + 1;
	for (auto v: adj[u]) {
		root[v] = u, change(v);
		if (sz[u] < 60 && v ^ adj[u][0])
			go(v, sz[u]);
	}
	int tmp = 60 - sz[adj[u][0]];
	go_big(adj[u][0], tmp);
}

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

void build_tree() {
	set_root(0);
	if (!~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);
}
/* In the name of Allah */
#include<bits/stdc++.h>
#include<Ioi.h>
using namespace std;

const int N = 1e4 + 5;
int n, m, 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, int &ted) {
	id[u] = ted++;
	path[root[u]].push_back(u);
	for (auto v: adj[u])
		if (ted < 60) {
			go(v, ted);
			path[root[u]].push_back(u);
		}
}

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

void build(int u) {
	vector<int> help;
	sz[u] = 1, down[u] = 0;
	for (auto v: adj[u]) {
		build(v);
		if (!~root[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;
	sz[root[u] = u] = sz[adj[u][id[u] = 0]] + 1;
	for (auto v: adj[u]) {
		root[v] = u, change(v);
		if (sz[u] < 60 && v ^ adj[u][0]) {
			go(v, sz[u]);
			path[u].push_back(u);
		}
	}
	int tmp = 60 - sz[adj[u][0]];
	go_big(adj[u][0], tmp);
}

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

void build_tree() {
	set_root(0);
	if (!~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;
			}
		}
	for (int i = 0; i < n; i++)
		assert(root[i] != -1);
}

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]) {
		V = Move(P = u);
		answer |= 1LL * V << id[P];
	}
	return answer;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 2296 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 7892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2288 KB Output is correct
2 Correct 10 ms 2160 KB Output is correct
3 Correct 10 ms 2256 KB Output is correct
4 Correct 14 ms 2836 KB Output is correct
5 Correct 14 ms 2960 KB Output is correct
6 Correct 15 ms 2956 KB Output is correct
7 Correct 14 ms 2960 KB Output is correct
8 Correct 14 ms 2948 KB Output is correct
9 Correct 32 ms 7220 KB Output is correct
10 Correct 34 ms 7216 KB Output is correct
11 Correct 31 ms 7344 KB Output is correct
12 Correct 10 ms 2128 KB Output is correct
13 Correct 10 ms 2036 KB Output is correct
14 Correct 10 ms 1908 KB Output is correct
15 Correct 10 ms 2156 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 7648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 8236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -