Submission #39817

#	Time	Username	Problem	Language	Result	Execution time	Memory
39817		UncleGrandpa925	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	35 ms	7208 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define bit(x,y) ((x>>(y))&1LL)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

// start of the common part
	int par[NMAX + 5], child[NMAX + 5], numcc = 0;
	vector<vector<int> > a(NMAX + 5); bool mark[60]; int lab[NMAX + 5]; int whcc[NMAX + 5]; int szcc[NMAX + 5];
	struct dsu {
		int par[NMAX + 5];
		dsu() {
			for (int i = 0; i < NMAX; i++) par[i] = i;
		}
		int find(int x) {
			if (par[x] == x) return x;
			return par[x] = find(par[x]);
		}
		void uni(int x, int y) {
			x = find(x); y = find(y);
			if (x != y) par[x] = y;
		}
	} d;
	void dfs(int u, int p) {
		child[u] = 1;
		for (auto v : a[u]) {
			if (v == p) continue;
			par[v] = u;
			dfs(v, u);
			child[u] += child[v];
		}
	}
	void makeTree(int N, int M, int A[], int B[]) {
		for (int i = 0; i < M; i++) {
			if (d.find(A[i]) != d.find(B[i])) {
				d.uni(A[i], B[i]);
				a[A[i]].push_back(B[i]);
				a[B[i]].push_back(A[i]);
			}
		}
		dfs(0, 0);
	}
	void preMark(int u, int p, int &rem, const int key) {
		if (rem == 0) return;
		mark[lab[u]] = true; rem--;
		for (auto v : a[u]) {
			if (whcc[v] != key || v == p) continue;
			preMark(v, u, rem, key);
			if (rem == 0) return;
		}
	}
	void fullMark(int u, int p, int &it, const long long X, int key) {
		whcc[u] = key; szcc[key]++;
		while (mark[it] && it < 59)
			it++;
		lab[u] = it; MessageBoard(u, bit(X, it)); mark[it] = true; it++;
		if (it == 60) return;
		for (auto v : a[u]) {
			if (v == p) continue;
			fullMark(v, u, it, X, key);
			if (it == 60) return;
		}
	}
	void dfs2(int u, int p, const long long X) {
		if (lab[u] == -1) {
			memset(mark, 0, sizeof(mark));
			int rem = 60 - min(60, child[u]);
			preMark(par[u], u, rem, whcc[par[u]]);
			int it = 0;
			fullMark(u, par[u], it, X, ++numcc);
		}
		for (auto v : a[u]) {
			if (v == p) continue;
			dfs2(v, u, X);
		}
	}
// end of the common part
	void Joi(int N, int M, int A[], int B[], long long X, int T) {
		memset(lab, -1, sizeof(lab));
		makeTree(N, M, A, B);
		dfs2(0, 0, X);
	}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define bit(x,y) ((x>>(y))&1LL)
#define NMAX 10000
#define MMAX 20000
#define MOVEMAX 20000

int par[NMAX + 5], child[NMAX + 5], numcc = 0;
vector<vector<int> > a(NMAX + 5); bool mark[60]; int lab[NMAX + 5]; int whcc[NMAX + 5]; int szcc[NMAX + 5];
struct dsu {
	int par[NMAX + 5];
	dsu() {
		for (int i = 0; i < NMAX; i++) par[i] = i;
	}
	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}
	void uni(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) par[x] = y;
	}
} d;
void dfs(int u, int p) {
	child[u] = 1;
	for (auto v : a[u]) {
		if (v == p) continue;
		par[v] = u;
		dfs(v, u);
		child[u] += child[v];
	}
}
void makeTree(int N, int M, int A[], int B[]) {
	for (int i = 0; i < M; i++) {
		if (d.find(A[i]) != d.find(B[i])) {
			d.uni(A[i], B[i]);
			a[A[i]].push_back(B[i]);
			a[B[i]].push_back(A[i]);
		}
	}
	dfs(0, 0);
}
void preMark(int u, int p, int &rem, const int key, int root) {
	if (rem == 0) return;
	mark[lab[u]] = true; rem--;
	for (auto v : a[u]) {
		if (whcc[v] != key || v == p) continue;
		preMark(v, u, rem, key, root);
		if (rem == 0) return;
	}
}
void fullMark(int u, int p, int &it, int key, int root) {
	whcc[u] = key; szcc[key]++;
	while (mark[it] && it < 59)
		it++;
	lab[u] = it; mark[it] = true; it++;
	if (it == 60) return;
	for (auto v : a[u]) {
		if (v == p) continue;
		fullMark(v, u, it, key, root);
		if (it == 60) return;
	}
}
void dfs2(int u, int p) {
	if (lab[u] == -1) {
		memset(mark, 0, sizeof(mark));
		int rem = 60 - min(60, child[u]);
		preMark(par[u], u, rem, whcc[par[u]], u);
		int it = 0;
		fullMark(u, par[u], it, ++numcc, u);
	}
	for (auto v : a[u]) {
		if (v == p) continue;
		dfs2(v, u);
	}
}
// start of Ioi part
long long ret = 0;
void dfs3(int u, int p, const int key, int Z) {
	if (Z) ret ^= (1LL << lab[u]);
	for (auto v : a[u]) {
		if (v == p || whcc[v] != key) continue;
		dfs3(v, u, key, Move(v));
	}
	if (u != p) Move(p);
}
const int INF = 1e9;
void dfs4(int u, int p, int &rem, const int key) {
	whcc[u] = INF; rem--;
	if (rem == 0) return;
	for (auto v : a[u]) {
		if (whcc[v] != key || v == p) continue;
		dfs4(v, u, rem, key);
		if (rem == 0) return;
	}
}
void dfs2x(int u, int Z) {
	if (szcc[whcc[u]] >= 60) {
		dfs3(u, u, whcc[u], Z);
		return;
	}
	int ori = u;
	while (u != 0 && szcc[whcc[par[u]]] < 60) {
		u = par[u];
	}
	int rem = 60 - min(60, child[u]);
	dfs4(par[u], u, rem, whcc[par[u]]);
	dfs4(u, par[u], child[u], whcc[u]);
	dfs3(ori, ori, INF, Z);
}
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	memset(lab, -1, sizeof(lab));
	makeTree(N, M, A, B);
	dfs2(0, 0);
	dfs2x(P, V);
	return ret;
}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17