Submission #67561

#	Time	Username	Problem	Language	Result	Execution time	Memory
67561		kingpig9	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	560 ms	160696 KiB

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 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17