oj.uz

Submission #205637

# Submission time Handle Problem Language Result Execution time Memory
205637 2020-02-29T11:07:21 Z ArshiaDadras Amusement Park (JOI17_amusement_park) C++14
10 / 100
 50 ms 7340 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;
			}
		}
}

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 1908 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2036 KB Output is correct
2 Correct 12 ms 2148 KB Output is correct
3 Correct 10 ms 2040 KB Output is correct
4 Correct 14 ms 2980 KB Output is correct
5 Correct 14 ms 2852 KB Output is correct
6 Correct 13 ms 2960 KB Output is correct
7 Correct 15 ms 2980 KB Output is correct
8 Correct 16 ms 2936 KB Output is correct
9 Correct 37 ms 7340 KB Output is correct
10 Correct 36 ms 7324 KB Output is correct
11 Correct 37 ms 7208 KB Output is correct
12 Correct 11 ms 2040 KB Output is correct
13 Correct 12 ms 2200 KB Output is correct
14 Correct 12 ms 2080 KB Output is correct
15 Correct 10 ms 2136 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5588 KB Output is correct
2 Incorrect 47 ms 5916 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5576 KB Output is correct
2 Incorrect 47 ms 5748 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -