Submission #67561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
67561	2018-08-15T01:18:12 Z	kingpig9	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	560 ms	160696 KB

Joi

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 10010;
static const int MAGIC = 60;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static int N, M;
static vector<int> adj[MAXN];
static map<int, vector<int>> tree[MAXN];
static int ord[MAXN];
static bool done[MAXN];
static int label[MAXN];

static void dfs1 (int x, int p) {
	static int cur = 0;
	ord[x] = cur++;
	for (int y : adj[x]) {
		if (y != p) {
			dfs1(y, x);
		}
	}
}

static void dfs (int x, int p) {
	//based on p, create a tree for x.
	int adel, bdel;
	for (auto it : tree[p]) {
		if (it.se.size() == 1) {
			if (it.se[0] != p && it.fi != p) {
				adel = it.fi;
				bdel = it.se[0];
			}
		}
	}
	//debug("tree[%d] assign as tree[%d]\n", x, p);
	//debug("but erase %d %d\n", adel, bdel);
	tree[x] = tree[p];
	vector<int> &va = tree[x].at(adel), &vb = tree[x].at(bdel);
	va.erase(find(all(va), bdel));
	vb.erase(find(all(vb), adel));
	if (va.empty()) {
		tree[x].erase(adel);
	}
	if (vb.empty()) {
		tree[x].erase(bdel);
	}

	//now add edge x -> p.
	label[x] = label[adel];
	tree[x][x].push_back(p);
	tree[x][p].push_back(x);

	for (int y : adj[x]) {
		if (y != p) {
			dfs(y, x);
		}
	}
}

void Joi (int nnn, int mmm, int aaa[], int bbb[], ll X, int subtask) {
	N = nnn;
	M = mmm;

	assert(N >= MAGIC);
	assert(X < (1ll << MAGIC));
	vector<pii> edges;
	for (int i = 0; i < M; i++) {
		edges.push_back({aaa[i], bbb[i]});
	}
	sort(all(edges));

	//ok let's assign it!
	struct {
		int par[MAXN];

		void init() {
			for (int i = 0; i < N; i++) {
				par[i] = i;
			}
		}

		int find (int x) {
			return x == par[x] ? x : par[x] = find(par[x]);
		}

		bool merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return false;
			}
			par[x] = y;
			return true;
		}
	} uf;

	uf.init();
	for (int i = 0; i < M; i++) {
		if (uf.merge(edges[i].fi, edges[i].se)) {
			adj[edges[i].fi].push_back(edges[i].se);
			adj[edges[i].se].push_back(edges[i].fi);
		}
	}

	//ok start with a 60
	dfs1(0, -1);
	vector<pii> tfirst;
	for (int i = 0; i < N; i++) {
		for (int j : adj[i]) {
			if (ord[i] < MAGIC && ord[j] < MAGIC) {
				tfirst.push_back({i, j});
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (ord[i] < MAGIC) {
			label[i] = ord[i];
			done[i] = true;
			for (pii p : tfirst) {
				tree[i][p.fi].push_back(p.se);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (ord[i] < MAGIC) {
			for (int j : adj[i]) {
				if (!done[j]) {
					dfs(j, i);
				}
			}
		}
	}

	/*
	for (int i = 0; i < N; i++) {
		debug("label[%d] = %d\n", i, label[i]);
	}
	*/

	for (int i = 0; i < N; i++) {
		MessageBoard(i, (X >> label[i]) & 1);
	}
}

Ioi

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 10010;
static const int MAGIC = 60;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static int N, M;
static vector<int> adj[MAXN];
static map<int, vector<int>> tree[MAXN];
static int ord[MAXN];
static bool done[MAXN];
static int label[MAXN];

static void dfs1 (int x, int p) {
	static int cur = 0;
	ord[x] = cur++;
	for (int y : adj[x]) {
		if (y != p) {
			dfs1(y, x);
		}
	}
}

static void dfs (int x, int p) {
	//based on p, create a tree for x.
	int adel, bdel;
	for (auto it : tree[p]) {
		if (it.se.size() == 1) {
			if (it.se[0] != p && it.fi != p) {
				adel = it.fi;
				bdel = it.se[0];
			}
		}
	}
	//debug("tree[%d] assign as tree[%d]\n", x, p);
	//debug("but erase %d %d\n", adel, bdel);
	tree[x] = tree[p];
	vector<int> &va = tree[x].at(adel), &vb = tree[x].at(bdel);
	va.erase(find(all(va), bdel));
	vb.erase(find(all(vb), adel));
	if (va.empty()) {
		tree[x].erase(adel);
	}
	if (vb.empty()) {
		tree[x].erase(bdel);
	}

	//now add edge x -> p.
	label[x] = label[adel];
	tree[x][x].push_back(p);
	tree[x][p].push_back(x);

	for (int y : adj[x]) {
		if (y != p) {
			dfs(y, x);
		}
	}
}

static map<int, vector<int>> mp;
static ll ans;

static void dfsans (int x, int p, int v) {
	if (v) {
		ans ^= (1ll << label[x]);
	}

	for (int y : mp[x]) {
		if (y != p) {
			//debug("%d -> %d\n", x, y);
			dfsans(y, x, Move(y));
			assert(Move(x) == v);
		}
	}
}

ll Ioi (int nnn, int mmm, int aaa[], int bbb[], int P, int V, int subtask) {
	N = nnn;
	M = mmm;

	assert(N >= MAGIC);

	vector<pii> edges;
	for (int i = 0; i < M; i++) {
		edges.push_back({aaa[i], bbb[i]});
	}
	sort(all(edges));

	//ok let's assign it!
	struct {
		int par[MAXN];

		void init() {
			for (int i = 0; i < N; i++) {
				par[i] = i;
			}
		}

		int find (int x) {
			return x == par[x] ? x : par[x] = find(par[x]);
		}

		bool merge (int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return false;
			}
			par[x] = y;
			return true;
		}
	} uf;

	uf.init();
	for (int i = 0; i < M; i++) {
		if (uf.merge(edges[i].fi, edges[i].se)) {
			adj[edges[i].fi].push_back(edges[i].se);
			adj[edges[i].se].push_back(edges[i].fi);
		}
	}

	//ok start with a 60
	dfs1(0, -1);
	vector<pii> tfirst;
	for (int i = 0; i < N; i++) {
		for (int j : adj[i]) {
			if (ord[i] < MAGIC && ord[j] < MAGIC) {
				tfirst.push_back({i, j});
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (ord[i] < MAGIC) {
			label[i] = ord[i];
			done[i] = true;
			for (pii p : tfirst) {
				tree[i][p.fi].push_back(p.se);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (ord[i] < MAGIC) {
			for (int j : adj[i]) {
				if (!done[j]) {
					dfs(j, i);
				}
			}
		}
	}

	/*
	for (int i = 0; i < N; i++) {
		debug("label[%d] = %d\n", i, label[i]);
	}
	*/

	mp = tree[P];
	dfsans(P, -1, V);
	return ans;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	3056 KB	Output is correct
2	Correct	12 ms	4392 KB	Output is correct
3	Correct	20 ms	6696 KB	Output is correct
4	Correct	13 ms	6696 KB	Output is correct
5	Correct	11 ms	6696 KB	Output is correct
6	Correct	15 ms	6696 KB	Output is correct
7	Correct	16 ms	6816 KB	Output is correct
8	Correct	14 ms	6924 KB	Output is correct
9	Correct	14 ms	7008 KB	Output is correct
10	Correct	11 ms	7008 KB	Output is correct
11	Correct	17 ms	7008 KB	Output is correct
12	Correct	9 ms	7008 KB	Output is correct
13	Correct	20 ms	7056 KB	Output is correct
14	Correct	20 ms	7100 KB	Output is correct
15	Correct	23 ms	7124 KB	Output is correct
16	Correct	20 ms	7132 KB	Output is correct
17	Correct	18 ms	7140 KB	Output is correct
18	Correct	16 ms	7264 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	381 ms	137408 KB	Output is correct
2	Correct	370 ms	137824 KB	Output is correct
3	Correct	387 ms	138148 KB	Output is correct
4	Correct	351 ms	138248 KB	Output is correct
5	Correct	351 ms	138944 KB	Output is correct
6	Correct	366 ms	139120 KB	Output is correct
7	Correct	396 ms	139120 KB	Output is correct
8	Correct	416 ms	139272 KB	Output is correct
9	Correct	364 ms	139516 KB	Output is correct
10	Correct	457 ms	147108 KB	Output is correct
11	Correct	521 ms	147224 KB	Output is correct
12	Correct	381 ms	147224 KB	Output is correct
13	Correct	320 ms	147224 KB	Output is correct
14	Correct	340 ms	147224 KB	Output is correct
15	Correct	337 ms	147224 KB	Output is correct
16	Correct	345 ms	147224 KB	Output is correct
17	Correct	366 ms	147224 KB	Output is correct
18	Correct	373 ms	147224 KB	Output is correct
19	Correct	380 ms	147224 KB	Output is correct
20	Correct	331 ms	147224 KB	Output is correct
21	Correct	335 ms	147224 KB	Output is correct
22	Correct	399 ms	147224 KB	Output is correct
23	Correct	401 ms	147224 KB	Output is correct
24	Correct	364 ms	147224 KB	Output is correct
25	Correct	508 ms	147224 KB	Output is correct
26	Correct	364 ms	147224 KB	Output is correct
27	Correct	397 ms	147224 KB	Output is correct
28	Correct	386 ms	147224 KB	Output is correct
29	Correct	447 ms	147224 KB	Output is correct
30	Correct	395 ms	147224 KB	Output is correct
31	Correct	11 ms	147224 KB	Output is correct
32	Correct	13 ms	147224 KB	Output is correct
33	Correct	18 ms	147224 KB	Output is correct
34	Correct	10 ms	147224 KB	Output is correct
35	Correct	10 ms	147224 KB	Output is correct
36	Correct	9 ms	147224 KB	Output is correct
37	Correct	9 ms	147224 KB	Output is correct
38	Correct	9 ms	147224 KB	Output is correct
39	Correct	8 ms	147224 KB	Output is correct
40	Correct	10 ms	147224 KB	Output is correct
41	Correct	12 ms	147224 KB	Output is correct
42	Correct	9 ms	147224 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	147224 KB	Output is correct
2	Correct	10 ms	147224 KB	Output is correct
3	Correct	11 ms	147224 KB	Output is correct
4	Correct	59 ms	147224 KB	Output is correct
5	Correct	58 ms	147224 KB	Output is correct
6	Correct	73 ms	147224 KB	Output is correct
7	Correct	92 ms	147224 KB	Output is correct
8	Correct	63 ms	147224 KB	Output is correct
9	Correct	374 ms	147224 KB	Output is correct
10	Correct	329 ms	147224 KB	Output is correct
11	Correct	333 ms	147224 KB	Output is correct
12	Correct	8 ms	147224 KB	Output is correct
13	Correct	8 ms	147224 KB	Output is correct
14	Correct	9 ms	147224 KB	Output is correct
15	Correct	10 ms	147224 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	147224 KB	Output is correct
2	Correct	412 ms	147224 KB	Output is correct
3	Correct	374 ms	147224 KB	Output is correct
4	Correct	346 ms	147224 KB	Output is correct
5	Correct	378 ms	147224 KB	Output is correct
6	Correct	379 ms	147224 KB	Output is correct
7	Correct	353 ms	147224 KB	Output is correct
8	Correct	412 ms	147224 KB	Output is correct
9	Correct	359 ms	147224 KB	Output is correct
10	Correct	435 ms	153576 KB	Output is correct
11	Correct	471 ms	154096 KB	Output is correct
12	Correct	356 ms	154288 KB	Output is correct
13	Correct	321 ms	154288 KB	Output is correct
14	Correct	407 ms	154288 KB	Output is correct
15	Correct	357 ms	154288 KB	Output is correct
16	Correct	340 ms	154288 KB	Output is correct
17	Correct	352 ms	154288 KB	Output is correct
18	Correct	408 ms	154288 KB	Output is correct
19	Correct	421 ms	154288 KB	Output is correct
20	Correct	429 ms	154288 KB	Output is correct
21	Correct	369 ms	154288 KB	Output is correct
22	Correct	394 ms	154288 KB	Output is correct
23	Correct	429 ms	154288 KB	Output is correct
24	Correct	381 ms	154288 KB	Output is correct
25	Correct	437 ms	154288 KB	Output is correct
26	Correct	426 ms	154288 KB	Output is correct
27	Correct	393 ms	154288 KB	Output is correct
28	Correct	416 ms	154288 KB	Output is correct
29	Correct	352 ms	154288 KB	Output is correct
30	Correct	398 ms	154288 KB	Output is correct

Subtask #5

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	407 ms	154288 KB	Output is correct
2	Correct	422 ms	154288 KB	Output is correct
3	Correct	413 ms	154288 KB	Output is correct
4	Correct	339 ms	154288 KB	Output is correct
5	Correct	350 ms	154288 KB	Output is correct
6	Correct	379 ms	154288 KB	Output is correct
7	Correct	416 ms	154288 KB	Output is correct
8	Correct	405 ms	154288 KB	Output is correct
9	Correct	433 ms	154288 KB	Output is correct
10	Correct	560 ms	160276 KB	Output is correct
11	Correct	473 ms	160544 KB	Output is correct
12	Correct	380 ms	160696 KB	Output is correct
13	Correct	382 ms	160696 KB	Output is correct
14	Correct	365 ms	160696 KB	Output is correct
15	Correct	376 ms	160696 KB	Output is correct
16	Correct	347 ms	160696 KB	Output is correct
17	Correct	332 ms	160696 KB	Output is correct
18	Correct	395 ms	160696 KB	Output is correct
19	Correct	381 ms	160696 KB	Output is correct
20	Correct	344 ms	160696 KB	Output is correct
21	Correct	311 ms	160696 KB	Output is correct
22	Correct	450 ms	160696 KB	Output is correct
23	Correct	389 ms	160696 KB	Output is correct
24	Correct	411 ms	160696 KB	Output is correct
25	Correct	412 ms	160696 KB	Output is correct
26	Correct	425 ms	160696 KB	Output is correct
27	Correct	432 ms	160696 KB	Output is correct
28	Correct	399 ms	160696 KB	Output is correct
29	Correct	385 ms	160696 KB	Output is correct
30	Correct	389 ms	160696 KB	Output is correct
31	Correct	13 ms	160696 KB	Output is correct
32	Correct	16 ms	160696 KB	Output is correct
33	Correct	20 ms	160696 KB	Output is correct
34	Correct	14 ms	160696 KB	Output is correct
35	Correct	28 ms	160696 KB	Output is correct
36	Correct	11 ms	160696 KB	Output is correct
37	Correct	10 ms	160696 KB	Output is correct
38	Correct	9 ms	160696 KB	Output is correct
39	Correct	8 ms	160696 KB	Output is correct
40	Correct	11 ms	160696 KB	Output is correct
41	Correct	10 ms	160696 KB	Output is correct
42	Correct	11 ms	160696 KB	Output is correct