oj.uz

답안 #205646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205646 2020-02-29T11:20:19 Z ArshiaDadras Amusement Park (JOI17_amusement_park) C++14
10 / 100
 51 ms 7212 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 1916 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 5552 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2280 KB Output is correct
2 Correct 10 ms 2256 KB Output is correct
3 Correct 10 ms 2252 KB Output is correct
4 Correct 14 ms 2844 KB Output is correct
5 Correct 14 ms 2836 KB Output is correct
6 Correct 13 ms 2960 KB Output is correct
7 Correct 13 ms 3092 KB Output is correct
8 Correct 15 ms 2836 KB Output is correct
9 Correct 39 ms 7112 KB Output is correct
10 Correct 32 ms 7056 KB Output is correct
11 Correct 30 ms 7212 KB Output is correct
12 Correct 11 ms 1908 KB Output is correct
13 Correct 10 ms 2296 KB Output is correct
14 Correct 10 ms 2136 KB Output is correct
15 Correct 10 ms 2036 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 5460 KB Output is correct
2 Incorrect 45 ms 5712 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 5600 KB Output is correct
2 Incorrect 39 ms 5584 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -