oj.uz

Submission #205629

# Submission time Handle Problem Language Result Execution time Memory
205629 2020-02-29T10:45:13 Z ArshiaDadras Amusement Park (JOI17_amusement_park) C++14
0 / 100
 45 ms 5976 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] = 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] = 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 |= V << id[P];
	}
	return answer;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

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

Subtask #5
0 / 17.0

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