oj.uz

Submission #46562

# Submission time Handle Problem Language Result Execution time Memory
46562 2018-04-21T12:21:04 Z qoo2p5 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 446 ms 14088 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);
	}
}

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 {
		what[center] = 0;
		vector<pair<int, int>> q;
		for (int u : g[center]) {
			q.pb({dist[u], u});
		}
		sort(all(q));
		reverse(all(q));
		int ptr = K - 1;
		for (auto &it : q) {
			int u = it.second;
			periodic_color(u, ptr, -1);
			ptr -= dist[u] + 1;
			if (ptr <= 0) {
				break;
			}
		}
	}
	
	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);
	}
}

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) {
		assert(know[i] == 0 || know[i] == 1);
		ans += (know[i] << i);
	}
	return ans;
}

int v;
set<pair<int, int>> wtf;

void go(int to) {
	static int steps = 0;
	steps++;
	assert(steps <= 500);
	assert(wtf.count({v, to}));
	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;
	rep(i, 0, mm) {
		wtf.insert({A[i], B[i]});
		wtf.insert({B[i], A[i]});
	}
	
	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 {
		auto beg = clock();
		while ((clock() - beg) * 1.0 / CLOCKS_PER_SEC < 0.4);
		what[center] = 0;
		vector<pair<int, int>> q;
		for (int u : g[center]) {
			q.pb({dist[u], u});
		}
		sort(all(q));
		reverse(all(q));
		int ptr = K - 1;
		for (auto &it : q) {
			int u = it.second;
			periodic_color(u, ptr, -1);
			ptr -= dist[u] + 1;
			if (ptr <= 0) {
				break;
			}
		}
		
		know[what[v]] = num;
		while (p[v] != -1) {
			go(p[v]);
			if (known()) {
				break;
			}
		}
		
		for (auto &it : q) {
			if (known()) {
				break;
			}
			assert(v == center);
			go(it.second);
			while (sz(g[v]) && !known()) {
				int u = *max_element(all(g[v]), [&] (int x, int y) {
					return dist[x] < dist[y];
				});
				go(u);
			}
			if (known()) {
				break;
			}
			while (p[v] != -1) {
				go(p[v]);
				if (known()) {
					break;
				}
			}
		}
	}
	
	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
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7416 KB Output is correct
2 Correct 52 ms 9304 KB Output is correct
3 Correct 53 ms 9408 KB Output is correct
4 Correct 433 ms 9448 KB Output is correct
5 Correct 33 ms 9448 KB Output is correct
6 Correct 33 ms 9448 KB Output is correct
7 Correct 40 ms 9448 KB Output is correct
8 Correct 34 ms 9448 KB Output is correct
9 Correct 33 ms 9448 KB Output is correct
10 Correct 434 ms 9448 KB Output is correct
11 Runtime error 433 ms 10916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 12384 KB Output is correct
2 Correct 405 ms 12384 KB Output is correct
3 Correct 406 ms 12384 KB Output is correct
4 Correct 8 ms 12384 KB Output is correct
5 Correct 8 ms 12384 KB Output is correct
6 Correct 9 ms 12384 KB Output is correct
7 Correct 11 ms 12384 KB Output is correct
8 Correct 8 ms 12384 KB Output is correct
9 Correct 33 ms 13248 KB Output is correct
10 Correct 26 ms 14084 KB Output is correct
11 Correct 26 ms 14088 KB Output is correct
12 Correct 404 ms 14088 KB Output is correct
13 Correct 405 ms 14088 KB Output is correct
14 Correct 405 ms 14088 KB Output is correct
15 Correct 404 ms 14088 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 14088 KB Output is correct
2 Correct 52 ms 14088 KB Output is correct
3 Correct 51 ms 14088 KB Output is correct
4 Partially correct 435 ms 14088 KB Partially correct
5 Correct 34 ms 14088 KB Output is correct
6 Correct 33 ms 14088 KB Output is correct
7 Correct 46 ms 14088 KB Output is correct
8 Correct 38 ms 14088 KB Output is correct
9 Correct 38 ms 14088 KB Output is correct
10 Correct 434 ms 14088 KB Output is correct
11 Correct 442 ms 14088 KB Output is correct
12 Runtime error 431 ms 14088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14088 KB Output is correct
2 Correct 51 ms 14088 KB Output is correct
3 Correct 63 ms 14088 KB Output is correct
4 Correct 446 ms 14088 KB Output is correct
5 Correct 34 ms 14088 KB Output is correct
6 Correct 34 ms 14088 KB Output is correct
7 Correct 35 ms 14088 KB Output is correct
8 Correct 40 ms 14088 KB Output is correct
9 Correct 33 ms 14088 KB Output is correct
10 Correct 435 ms 14088 KB Output is correct
11 Correct 435 ms 14088 KB Output is correct
12 Runtime error 429 ms 14088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -