Submission #49588

#	Time	Username	Problem	Language	Result	Execution time	Memory
49588		WLZ	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	481 ms	71368 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
	private: vector<int> p, rank;
	public:
		DSU(int n) {
			p.assign(n, -1);
			rank.assign(n , 0);
		}
		int root(int x) {
			return p[x] < 0 ? x : p[x] = root(p[x]);
		}
		bool sameSet(int x, int y) {
			return root(x) == root(y);
		}
		void connect(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (rank[x] > rank[y]) p[y] = x;
				else {
					p[x] = y;
					if (rank[x] == rank[y]) rank[y]++;
				}
			}
		}
};

struct Vertex {
	//bool isLeaf;
	int bitIdx;
	set<int> subTree;
	Vertex() {
		bitIdx = -1;
	}	
};

vector<Vertex> nodes;
vector<vector<int>> g;
vector<int> curTree;
int cnt = 0;

void dfs1(int u, int par) {
	curTree.emplace_back(u);
	cnt++;
	if (cnt >= 60) return;
	//if ((int) g[u].size() == 1) nodes[u].isLeaf = true;
	for (auto& v : g[u]) {
		if (v != par) {
			dfs1(v, u);
			if (cnt >= 60) return;
		}
	}
	return;
}

int findLeaf(const set<int>& st, int exclude) {
	for (auto& u : st) {
		if (u == exclude) continue;
		int cnt = 0;
		for (auto& v : g[u]) {
			if (st.count(v)) cnt++;
		}
		if (cnt <= 1) return u;
	}
}

void dfs2(int u, int par) {
	if (nodes[u].bitIdx == -1) {
		int findV = findLeaf(nodes[par].subTree, par);
		nodes[u].subTree = nodes[par].subTree;
		nodes[u].subTree.erase(findV);
		nodes[u].subTree.insert(u);
		nodes[u].bitIdx = nodes[findV].bitIdx;
	}
	for (auto& v : g[u]) {
		if (v != par) {
			dfs2(v, u);
		}
	}
	return;
}

void Joi(int N, int M, int A[], int B[], long long X, int T) {
	g.resize(N);
	DSU dsu(N);
	nodes.resize(N);
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			g[A[i]].emplace_back(B[i]);
			g[B[i]].emplace_back(A[i]);
		}
	}
	dfs1(0, -1);
	for (int i = 0; i < 60; i++) {
		nodes[curTree[i]].bitIdx = i;
		for (int j = 0; j < 60; j++) nodes[curTree[i]].subTree.insert(curTree[j]);
	}
	dfs2(0, -1);
	vector<int> bin;
	for (int i = 0; i < 60; i++) {
		if (X & (1ll << i)) bin.emplace_back(1);
		else bin.emplace_back(0);
	}
	for (int i = 0; i < N; i++) {
		MessageBoard(i, bin[nodes[i].bitIdx]);
	}
	return;
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
	private: vector<int> p, rank;
	public:
		DSU(int n) {
			p.assign(n, -1);
			rank.assign(n , 0);
		}
		int root(int x) {
			return p[x] < 0 ? x : p[x] = root(p[x]);
		}
		bool sameSet(int x, int y) {
			return root(x) == root(y);
		}
		void connect(int x, int y) {
			x = root(x);
			y = root(y);
			if (x != y) {
				if (rank[x] > rank[y]) p[y] = x;
				else {
					p[x] = y;
					if (rank[x] == rank[y]) rank[y]++;
				}
			}
		}
};

struct Vertex {
	//bool isLeaf;
	int bitIdx;
	set<int> subTree;
	Vertex() {
		bitIdx = -1;
	}	
};

static vector<vector<int>> g;
static vector<Vertex> nodes;
static vector<int> curTree;
static int cnt = 0;
vector<int> binAns(60, 0);

static void dfs1(int u, int par) {
	curTree.emplace_back(u);
	cnt++;
	if (cnt >= 60) return;
	//if ((int) g[u].size() == 1) nodes[u].isLeaf = true;
	for (auto& v : g[u]) {
		if (v != par) {
			dfs1(v, u);
			if (cnt >= 60) return;
		}
	}
	return;
}

static int findLeaf(const set<int>& st, int exclude) {
	for (auto& u : st) {
		if (u == exclude) continue;
		int cnt = 0;
		for (auto& v : g[u]) {
			if (st.count(v)) cnt++;
		}
		if (cnt <= 1) return u;
	}
}

static void dfs2(int u, int par) {
	if (nodes[u].bitIdx == -1) {
		int findV = findLeaf(nodes[par].subTree, par);
		nodes[u].subTree = nodes[par].subTree;
		nodes[u].subTree.erase(findV);
		nodes[u].subTree.insert(u);
		nodes[u].bitIdx = nodes[findV].bitIdx;
	}
	for (auto& v : g[u]) {
		if (v != par) {
			dfs2(v, u);
		}
	}
	return;
}

void findX(int u, int par, int source) {
	for (auto& v : g[u]) {
		if (v != par) {
			if (nodes[source].subTree.count(v)) {
				binAns[nodes[v].bitIdx] = Move(v);
				findX(v, u, source);
				Move(u);
			}
		}
	}
}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
	g.resize(N);
	nodes.resize(N);
	DSU dsu(N);
	for (int i = 0; i < M; i++) {
		if (!dsu.sameSet(A[i], B[i])) {
			dsu.connect(A[i], B[i]);
			g[A[i]].push_back(B[i]);
			g[B[i]].push_back(A[i]);
		}
	}
	dfs1(0, -1);
	for (int i = 0; i < 60; i++) {
		nodes[curTree[i]].bitIdx = i;
		for (int j = 0; j < 60; j++) nodes[curTree[i]].subTree.insert(curTree[j]);
	}
	dfs2(0, -1);
	binAns[nodes[P].bitIdx] = V;
	findX(P, -1, P);
	long long ans = 0ll;
	for (int i = 0; i < 60; i++) {
		if (binAns[i] == 1) ans += (1ll << i);
	}
	return ans;
}

Compilation message (stderr)

Joi.cpp: In function 'int findLeaf(const std::set<int>&, int)':
Joi.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Ioi.cpp: In function 'int findLeaf(const std::set<int>&, int)':
Ioi.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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