oj.uz

Submission #46574

# Submission time Handle Problem Language Result Execution time Memory
46574 2018-04-21T13:33:59 Z qoo2p5 Amusement Park (JOI17_amusement_park) C++17
100 / 100
 812 ms 237768 KB 
#include "Joi.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

static const int INF = (int) 1e9 + 1e6 + 123;
static const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back

static bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

static bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

static const int N = 20005;
static const int K = 60;

static int n;
static int p[N];
static vector<int> g[N];

static int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}

static bool unite(int u, int v) {
	u = get(u), v = get(v);
	if (u == v) {
		return 0;
	}
	p[u] = v;
	return 1;
}

static bool test(long long mask, int bit) {
	return mask & (1LL << bit);
}

static void add_edge(int u, int v) {
	g[u].pb(v);
	g[v].pb(u);
}

static int center;
static int center_dist = INF;

static int dist[N];

static void calc_dist(int v, int f = -1) {
	dist[v] = 0;
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		calc_dist(u, v);
		maxi(dist[v], dist[u] + 1);
	}
}

static void find_center(int v, int f = -1, int up = 0) {
	int max_dist = max(up, dist[v]);
	if (mini(center_dist, max_dist)) {
		center = v;
	}
	multiset<int> q;
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		q.insert(dist[u] + 2);
	}
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		q.erase(q.find(dist[u] + 2));
		int nup = up + 1;
		if (sz(q)) {
			maxi(nup, *q.rbegin());
		}
		find_center(u, v, nup);
		q.insert(dist[u] + 2);
	}
}

static void make_root(int v, int f = -1) {
	p[v] = f;
	int ptr = 0;
	int pos = -1;
	for (int u : g[v]) {
		if (u == f) {
			pos = ptr;
			ptr++;
			continue;
		}
		make_root(u, v);
		ptr++;
	}
	if (pos != -1) {
		g[v].erase(g[v].begin() + pos);
	}
}

static int what[N];

static void periodic_color(int v, int c, int dir) {
	what[v] = c;
	for (int u : g[v]) {
		periodic_color(u, (c + dir + K) % K, dir);
	}
}

struct Tree {
	map<int, set<int>> edges;
	
	void dfs(int v, vector<int> &path, int f = -1) {
		if (f != -1) path.pb(v);
		for (int u : edges[v]) {
			if (u == f) {
				continue;
			}
			dfs(u, path, v);
			path.pb(v);
		}
	}
	
	int find_leaf(int deny) {
		for (auto &it : edges) {
			if (it.first == deny) continue;
			if (sz(it.second) == 1) {
				return it.first;
			}
		}
		assert(0);
		return -1;
	}
	
	int extract_leaf(int deny) {
		int v = find_leaf(deny);
		int u = *edges[v].begin();
		edges[u].erase(v);
		edges.erase(v);
		return v;
	}
	
	void add_edge(int u, int v) {
		edges[u].insert(v);
		edges[v].insert(u);
	}
};

static Tree wtf[N];

static void easy_find(int v) {
	if (sz(wtf[center].edges) == K) {
		return;
	}
	
	for (int u : g[v]) {
		wtf[center].add_edge(v, u);
		easy_find(u);
		if (sz(wtf[center].edges) == K) {
			return;
		}
	}
}

static void meow(int v) {
	if (wtf[v].edges.empty()) {
		wtf[v] = wtf[p[v]];
		int col = what[wtf[v].extract_leaf(p[v])];
		what[v] = col;
		wtf[v].add_edge(v, p[v]);
	}
	for (int u : g[v]) {
		meow(u);
	}
}

void Joi(int nn, int mm, int A[], int B[], long long x, int T) {
	n = nn;
	rep(i, 0, n) p[i] = i;
	rep(i, 0, mm) {
		if (unite(A[i], B[i])) {
			add_edge(A[i], B[i]);
		}
	}
	
	calc_dist(0);
	find_center(0);
	make_root(center);
	calc_dist(center);
	if (dist[center] >= K - 1) {
		periodic_color(center, 0, +1);
	} else {
		easy_find(center);
		int ptr = 0;
		for (auto &it : wtf[center].edges) {
			int u = it.first;
			what[u] = ptr++;
			if (u != center) wtf[u] = wtf[center];
		}
		meow(center);
		rep(i, 0, n) {
			assert(sz(wtf[i].edges) == K);
			vector<bool> col(K);
			for (auto &it : wtf[i].edges) {
				int u = it.first;
				col[what[u]] = 1;
			}
			rep(i, 0, K) assert(col[i]);
		}
	}
	
	rep(i, 0, n) {
		MessageBoard(i, test(x, what[i]));
	}
}

#include "Ioi.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

static const int INF = (int) 1e9 + 1e6 + 123;
static const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back

static bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

static bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

static const int N = 20005;
static const int K = 60;

static int n;
static int p[N];
static vector<int> g[N];

static int get(int v) {
	return (p[v] == v ? v : (p[v] = get(p[v])));
}

static bool unite(int u, int v) {
	u = get(u), v = get(v);
	if (u == v) {
		return 0;
	}
	p[u] = v;
	return 1;
}

static bool test(long long mask, int bit) {
	return mask & (1LL << bit);
}

static void add_edge(int u, int v) {
	g[u].pb(v);
	g[v].pb(u);
}

static int center;
static int center_dist = INF;

static int dist[N];

static void calc_dist(int v, int f = -1) {
	dist[v] = 0;
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		calc_dist(u, v);
		maxi(dist[v], dist[u] + 1);
	}
}

static void find_center(int v, int f = -1, int up = 0) {
	int max_dist = max(up, dist[v]);
	if (mini(center_dist, max_dist)) {
		center = v;
	}
	multiset<int> q;
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		q.insert(dist[u] + 2);
	}
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		q.erase(q.find(dist[u] + 2));
		int nup = up + 1;
		if (sz(q)) {
			maxi(nup, *q.rbegin());
		}
		find_center(u, v, nup);
		q.insert(dist[u] + 2);
	}
}

static void make_root(int v, int f = -1) {
	p[v] = f;
	int ptr = 0;
	int pos = -1;
	for (int u : g[v]) {
		if (u == f) {
			pos = ptr;
			ptr++;
			continue;
		}
		make_root(u, v);
		ptr++;
	}
	if (pos != -1) {
		g[v].erase(g[v].begin() + pos);
	}
}

static int what[N];

static void periodic_color(int v, int c, int dir) {
	what[v] = c;
	for (int u : g[v]) {
		periodic_color(u, (c + dir + K) % K, dir);
	}
}

struct Tree {
	map<int, set<int>> edges;
	
	void dfs(int v, vector<int> &path, int f = -1) {
		if (f != -1) path.pb(v);
		for (int u : edges[v]) {
			if (u == f) {
				continue;
			}
			dfs(u, path, v);
			path.pb(v);
		}
	}
	
	int find_leaf(int deny) {
		for (auto &it : edges) {
			if (it.first == deny) continue;
			if (sz(it.second) == 1) {
				return it.first;
			}
		}
		assert(0);
		return -1;
	}
	
	int extract_leaf(int deny) {
		int v = find_leaf(deny);
		int u = *edges[v].begin();
		edges[u].erase(v);
		edges.erase(v);
		return v;
	}
	
	void add_edge(int u, int v) {
		edges[u].insert(v);
		edges[v].insert(u);
	}
	
	vector<int> get_path(int start) {
		vector<int> res;
		dfs(start, res);
		return res;
	}
};

static Tree wtf[N];

static void easy_find(int v) {
	if (sz(wtf[center].edges) == K) {
		return;
	}
	
	for (int u : g[v]) {
		wtf[center].add_edge(v, u);
		easy_find(u);
		if (sz(wtf[center].edges) == K) {
			return;
		}
	}
}

static void meow(int v) {
	if (wtf[v].edges.empty()) {
		wtf[v] = wtf[p[v]];
		int col = what[wtf[v].extract_leaf(p[v])];
		what[v] = col;
		wtf[v].add_edge(v, p[v]);
	}
	for (int u : g[v]) {
		meow(u);
	}
}

ll know[K];

bool known() {
	rep(i, 0, K) {
		if (know[i] == -1) {
			return 0;
		}
	}
	return 1;
}

ll answer() {
	ll ans = 0;
	rep(i, 0, K) {
		ans += (know[i] << i);
	}
	return ans;
}

int v;

void go(int to) {
	static int steps = 0;
	steps++;
	assert(steps <= 500);
	assert(0 <= to && to <= n - 1);
	int x = Move(to);
	v = to;
	know[what[v]] = x;
}

long long Ioi(int nn, int mm, int A[], int B[], int vv, int num, int T) {
	rep(i, 0, K) know[i] = -1;
	
	n = nn;
	rep(i, 0, n) p[i] = i;
	rep(i, 0, mm) {
		if (unite(A[i], B[i])) {
			add_edge(A[i], B[i]);
		}
	}
	
	calc_dist(0);
	find_center(0);
	make_root(center);
	calc_dist(center);
	v = vv;
	if (dist[center] >= K - 1) {
		periodic_color(center, 0, +1);
		
		know[what[v]] = num;
		while (p[v] != -1) {
			go(p[v]);
			if (known()) {
				break;
			}
		}
		while (!known()) {
			assert(sz(g[v]));
			int u = *max_element(all(g[v]), [&] (int x, int y) {
				return dist[x] < dist[y];
			});
			go(u);
		}
	} else {
		easy_find(center);
		int ptr = 0;
		for (auto &it : wtf[center].edges) {
			int u = it.first;
			what[u] = ptr++;
			if (u != center) wtf[u] = wtf[center];
		}
		meow(center);
		rep(i, 0, n) {
			vector<bool> col(K);
			for (auto &it : wtf[i].edges) {
				int u = it.first;
				col[what[u]] = 1;
			}
		}
		vector<int> path = wtf[v].get_path(v);
		for (int u : path) {
			go(u);
		}
	}
	
	return answer();
}

Compilation message

Ioi.cpp:54:13: warning: 'bool test(long long int, int)' defined but not used [-Wunused-function]
 static bool test(long long mask, int bit) {
             ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5168 KB Output is correct
2 Correct 14 ms 7008 KB Output is correct
3 Correct 19 ms 10452 KB Output is correct
4 Correct 10 ms 10504 KB Output is correct
5 Correct 11 ms 10504 KB Output is correct
6 Correct 16 ms 10504 KB Output is correct
7 Correct 6 ms 10504 KB Output is correct
8 Correct 18 ms 10528 KB Output is correct
9 Correct 17 ms 10528 KB Output is correct
10 Correct 12 ms 10528 KB Output is correct
11 Correct 18 ms 10528 KB Output is correct
12 Correct 8 ms 10528 KB Output is correct
13 Correct 22 ms 11080 KB Output is correct
14 Correct 20 ms 11148 KB Output is correct
15 Correct 20 ms 11208 KB Output is correct
16 Correct 18 ms 11208 KB Output is correct
17 Correct 22 ms 11208 KB Output is correct
18 Correct 19 ms 11208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 11208 KB Output is correct
2 Correct 38 ms 11208 KB Output is correct
3 Correct 41 ms 11208 KB Output is correct
4 Correct 596 ms 230116 KB Output is correct
5 Correct 28 ms 230176 KB Output is correct
6 Correct 28 ms 230176 KB Output is correct
7 Correct 28 ms 230176 KB Output is correct
8 Correct 30 ms 230176 KB Output is correct
9 Correct 31 ms 230176 KB Output is correct
10 Correct 721 ms 230176 KB Output is correct
11 Correct 756 ms 230176 KB Output is correct
12 Correct 527 ms 230176 KB Output is correct
13 Correct 540 ms 230176 KB Output is correct
14 Correct 520 ms 230176 KB Output is correct
15 Correct 538 ms 230176 KB Output is correct
16 Correct 572 ms 230208 KB Output is correct
17 Correct 550 ms 230536 KB Output is correct
18 Correct 552 ms 230800 KB Output is correct
19 Correct 550 ms 230980 KB Output is correct
20 Correct 24 ms 231160 KB Output is correct
21 Correct 22 ms 231160 KB Output is correct
22 Correct 27 ms 231160 KB Output is correct
23 Correct 31 ms 231160 KB Output is correct
24 Correct 30 ms 231160 KB Output is correct
25 Correct 30 ms 231160 KB Output is correct
26 Correct 28 ms 231160 KB Output is correct
27 Correct 27 ms 231160 KB Output is correct
28 Correct 36 ms 231160 KB Output is correct
29 Correct 30 ms 231160 KB Output is correct
30 Correct 27 ms 231160 KB Output is correct
31 Correct 13 ms 231160 KB Output is correct
32 Correct 16 ms 231160 KB Output is correct
33 Correct 19 ms 231160 KB Output is correct
34 Correct 12 ms 231160 KB Output is correct
35 Correct 11 ms 231160 KB Output is correct
36 Correct 10 ms 231160 KB Output is correct
37 Correct 8 ms 231160 KB Output is correct
38 Correct 8 ms 231160 KB Output is correct
39 Correct 8 ms 231160 KB Output is correct
40 Correct 10 ms 231160 KB Output is correct
41 Correct 10 ms 231160 KB Output is correct
42 Correct 8 ms 231160 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 231160 KB Output is correct
2 Correct 24 ms 231160 KB Output is correct
3 Correct 10 ms 231160 KB Output is correct
4 Correct 10 ms 231160 KB Output is correct
5 Correct 8 ms 231160 KB Output is correct
6 Correct 8 ms 231160 KB Output is correct
7 Correct 8 ms 231160 KB Output is correct
8 Correct 8 ms 231160 KB Output is correct
9 Correct 22 ms 231160 KB Output is correct
10 Correct 23 ms 231160 KB Output is correct
11 Correct 23 ms 231160 KB Output is correct
12 Correct 9 ms 231160 KB Output is correct
13 Correct 9 ms 231160 KB Output is correct
14 Correct 8 ms 231160 KB Output is correct
15 Correct 9 ms 231160 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 231160 KB Output is correct
2 Correct 51 ms 231160 KB Output is correct
3 Correct 39 ms 231160 KB Output is correct
4 Correct 583 ms 233160 KB Output is correct
5 Correct 28 ms 233272 KB Output is correct
6 Correct 28 ms 233272 KB Output is correct
7 Correct 30 ms 233272 KB Output is correct
8 Correct 30 ms 233272 KB Output is correct
9 Correct 33 ms 233272 KB Output is correct
10 Correct 724 ms 233272 KB Output is correct
11 Correct 792 ms 233400 KB Output is correct
12 Correct 536 ms 233400 KB Output is correct
13 Correct 530 ms 233400 KB Output is correct
14 Correct 511 ms 233400 KB Output is correct
15 Correct 577 ms 233400 KB Output is correct
16 Correct 542 ms 233496 KB Output is correct
17 Correct 571 ms 233736 KB Output is correct
18 Correct 617 ms 233980 KB Output is correct
19 Correct 619 ms 234252 KB Output is correct
20 Correct 23 ms 234408 KB Output is correct
21 Correct 20 ms 234408 KB Output is correct
22 Correct 33 ms 234408 KB Output is correct
23 Correct 28 ms 234408 KB Output is correct
24 Correct 27 ms 234408 KB Output is correct
25 Correct 28 ms 234408 KB Output is correct
26 Correct 32 ms 234408 KB Output is correct
27 Correct 27 ms 234408 KB Output is correct
28 Correct 28 ms 234408 KB Output is correct
29 Correct 29 ms 234408 KB Output is correct
30 Correct 28 ms 234408 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 234408 KB Output is correct
2 Correct 41 ms 234408 KB Output is correct
3 Correct 39 ms 234408 KB Output is correct
4 Correct 547 ms 236632 KB Output is correct
5 Correct 28 ms 236824 KB Output is correct
6 Correct 34 ms 236824 KB Output is correct
7 Correct 33 ms 236824 KB Output is correct
8 Correct 28 ms 236824 KB Output is correct
9 Correct 28 ms 236824 KB Output is correct
10 Correct 812 ms 236824 KB Output is correct
11 Correct 790 ms 236824 KB Output is correct
12 Correct 545 ms 236824 KB Output is correct
13 Correct 540 ms 236824 KB Output is correct
14 Correct 568 ms 236824 KB Output is correct
15 Correct 586 ms 236824 KB Output is correct
16 Correct 613 ms 236872 KB Output is correct
17 Correct 589 ms 237296 KB Output is correct
18 Correct 600 ms 237676 KB Output is correct
19 Correct 580 ms 237768 KB Output is correct
20 Correct 22 ms 237768 KB Output is correct
21 Correct 20 ms 237768 KB Output is correct
22 Correct 28 ms 237768 KB Output is correct
23 Correct 36 ms 237768 KB Output is correct
24 Correct 27 ms 237768 KB Output is correct
25 Correct 34 ms 237768 KB Output is correct
26 Correct 31 ms 237768 KB Output is correct
27 Correct 30 ms 237768 KB Output is correct
28 Correct 35 ms 237768 KB Output is correct
29 Correct 33 ms 237768 KB Output is correct
30 Correct 27 ms 237768 KB Output is correct
31 Correct 15 ms 237768 KB Output is correct
32 Correct 12 ms 237768 KB Output is correct
33 Correct 18 ms 237768 KB Output is correct
34 Correct 12 ms 237768 KB Output is correct
35 Correct 10 ms 237768 KB Output is correct
36 Correct 10 ms 237768 KB Output is correct
37 Correct 9 ms 237768 KB Output is correct
38 Correct 8 ms 237768 KB Output is correct
39 Correct 8 ms 237768 KB Output is correct
40 Correct 10 ms 237768 KB Output is correct
41 Correct 10 ms 237768 KB Output is correct
42 Correct 8 ms 237768 KB Output is correct