Submission #810537

#	Time	Username	Problem	Language	Result	Execution time	Memory
810537		Sohsoh84	Split the Attractions (IOI19_split)	C++17	0 / 100	2080 ms	24140 KiB

split

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

using namespace std;

typedef pair<int, int> pll;

#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;
#define X		first
#define Y		second
#define all(x)		(x).begin(), (x).end()

const int MAXN = 1e5 + 10;

pll cyc_edge;
vector<int> adjt[MAXN], adj[MAXN], nodes;
int a, b, c, n, m, ans[MAXN], sz[MAXN], T[4] = {0, 1, 2, 3}, ind[MAXN];
bool flag = false;
bool vis[MAXN];

inline bool check(int u, int v) {
	return false;
}

void dfs_ans(int v, int p, int c, int& cnt) {
	if (cnt) {
		ans[v] = c;
		cnt--;
	}

	for (int u : adj[v]) {
		if (u == p || check(u, v)) continue;
		dfs_ans(u, v, c, cnt);
	}
}

void dfs_tree(int v) {
	nodes.push_back(v);
	vis[v] = true;
	for (int u : adjt[v])
		if (!vis[u])
			dfs_tree(u), adj[v].push_back(u), adj[u].push_back(v);
}

int dist[MAXN];

void bfs_tree(int v) {
	memset(dist, 63, sizeof dist);
	queue<int> q;
	
	q.push(v);
	dist[v] = 0;

	while (!q.empty()) {
		int v = q.front();
		q.pop();
		nodes.push_back(v);

		for (int u : adj[v]) {
			if (dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				q.push(u);
				adj[u].push_back(v);
				adj[v].push_back(u);
			}
		}
	}
}

void dfs1(int v, int p) {
	sz[v] = 1;
	for (int u : adj[v]) {
		if (u == p || check(u, v)) continue;

		dfs1(u, v);
		sz[v] += sz[u];

		if (!flag && sz[u] >= a && n - sz[u] >= b) {
			flag = true;
			dfs_ans(u, v, 1, a);
			dfs_ans(v, u, 2, b);
		}

		if (!flag && sz[u] >= b && n - sz[u] >= a) {
			flag = true;
			dfs_ans(u, v, 2, b);
			dfs_ans(v, u, 1, a);
		}
	}
}

namespace DSU {
	int par[MAXN];

	inline void init() {
		for (int i = 1; i <= n; i++)
			par[i] = i;
	}

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

	inline bool unite(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return false;
		par[v] = u;
		
		return true;
	}
}

namespace DSU2 {
	int par[MAXN];
	vector<int> C[MAXN];
	set<pll> sz_st;

	inline void init() {
		sz_st.clear();
		for (int i = 1; i <= n; i++) {
			C[i].clear();
			par[i] = i;
			C[i].push_back(i);
			sz_st.insert(pll(1, i));
			adj[i].clear();
		}
	}
	
	inline bool unite(int u_, int v_) {
		int u = par[u_], v = par[v_];
		if (u == v) return false;
		adj[u_].push_back(v_);
		adj[v_].push_back(u_);
		if (C[u].size() < C[v].size()) swap(u, v);

		sz_st.erase(pll(C[v].size(), v));
		sz_st.erase(pll(C[u].size(), u));
		for (int e : C[v]) {
			par[e] = u;
			C[u].push_back(e);
		}

		sz_st.insert(pll(C[u].size(), u));
		C[v].clear();
		return true;
	}

	inline void check() {
		if (sz_st.size() >= 2 && prev(sz_st.end()) -> X >= b && prev(prev(sz_st.end())) -> X >= a) {
			flag = true;
			dfs_ans(prev(sz_st.end()) -> Y, 0, 2, b);	
			dfs_ans(prev(prev(sz_st.end())) -> Y, 0, 1, a);	
		}
	}

	inline int score(int u, int v) {
		if (par[u] == par[v]) return 100 * n;
		return C[par[u]].size() + C[par[v]].size();
	}
}

vector<int> find_split(int n_, int a_, int b_, int c_, vector<int> p_, vector<int> q_) {
	n = n_, a = a_, b = b_, c = c_;
	if (b > c) swap(b, c), swap(T[2], T[3]);
	if (a > c) swap(a, c), swap(T[1], T[3]);
	if (a > b) swap(a, b), swap(T[1], T[2]);
	
	m = p_.size();	
	vector<pll> edges;

	for (int i = 0; i < m; i++) {
		int u = p_[i], v = q_[i];
		u++, v++;
		adjt[u].push_back(v);
		adjt[v].push_back(u);
		edges.push_back({u, v});
	}	
	
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	int t = 100; // buggy
/*	while (t-- && !flag) {	
		for (int i = 1; i <= n; i++) adj[i].clear();

		shuffle(all(edges), rng);
		DSU::init();
		for (int i = 0; i < m; i++) {
			int u = edges[i].X, v = edges[i].Y;
			if (DSU::unite(u, v)) adj[u].push_back(v), adj[v].push_back(u);
			else cyc_edge = {u, v};
		}


		path.clear();
		if (cyc_edge.X) {
			dfs_path(cyc_edge.X, 0, cyc_edge.Y);

			adj[cyc_edge.X].push_back(cyc_edge.Y);
			adj[cyc_edge.Y].push_back(cyc_edge.X);
			for (int i = 0; i < int(path.size()) - 1; i++) {
				if (flag) break;

				cyc_edge = {path[i], path[i + 1]};
				dfs1(1, 0);
			}

			cyc_edge = {0, 0};
		}
	}
*/
	t = 1;
	while (t-- && !flag) {
		DSU2::init();
		shuffle(all(edges), rng);

		for (int k = 1; k < n && !flag; k++) {
			DSU2::check();
			if (flag) break;

			pll best = {0, 0};
			for (auto [u, v] : edges)
				if (best.X == 0 || DSU2::score(u, v) < DSU2::score(best.X, best.Y))
					 best = {u, v};

			DSU2::unite(best.X, best.Y);
		}
	}

	debug(flag)
	t = 300;

	while (t-- && !flag) {	
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			adj[i].clear(), vis[i] = false, shuffle(all(adjt[i]), rng);
		
		dfs_tree(v);
		dfs1(1, 0);
	}

	t = 150;
	while (t-- && !flag) {	
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			adj[i].clear(), shuffle(all(adjt[i]), rng);
		
		bfs_tree(v);
		dfs1(1, 0);
	}

	vector<int> nodes;
	for (int i = 1; i <= n; i++)
		nodes.push_back(i);

	t = 20;	
	while (t-- && !flag) {	
		DSU::init();
		shuffle(all(nodes), rng);
		for (int i = 1; i <= n; i++)
			adj[i].clear();

		for (int i = 0; i < n; i++) ind[nodes[i]] = i;
		for (int i = 0; i < n; i++) {
			int mn = -1;
			for (int u : adjt[nodes[i]]) {
				if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
						mn = u;
			}

			if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]), DSU::unite(mn, nodes[i]);
		}

		shuffle(all(edges), rng);
		for (auto [u, v] : edges)
			if (DSU::unite(u, v))
				adj[u].push_back(v), adj[v].push_back(u);

		dfs1(1, 0);
	}

	t = 20;
	while (t-- && !flag) {	
		nodes.clear();
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			vis[i] = false, shuffle(all(adjt[i]), rng);

		dfs_tree(v);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i < n; i++) ind[nodes[i]] = i;
		for (int i = 0; i < n; i++) {
			int mn = -1;
			for (int u : adjt[nodes[i]]) {
				if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
						mn = u;
			}

			if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
		}

		dfs1(1, 0);
	}


	t = 3000;
	while (t-- && !flag) {	
		nodes.clear();
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			vis[i] = false, shuffle(all(adjt[i]), rng);

		bfs_tree(v);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i < n; i++) ind[nodes[i]] = i;
		for (int i = 0; i < n; i++) {
			int mn = -1;
			for (int u : adjt[nodes[i]]) {
				if (ind[u] > i && (mn == -1 || ind[u] < ind[mn]))
						mn = u;
			}

			if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
		}

		dfs1(1, 0);
	}

	t = 1000;
	while (t-- && !flag) {	
		nodes.clear();
		int v = rng() % n + 1;
		for (int i = 1; i <= n; i++)
			vis[i] = false, shuffle(all(adjt[i]), rng);

		bfs_tree(v);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i < n; i++) ind[nodes[i]] = i;
		for (int i = 0; i < n; i++) {
			int mn = -1;
			for (int u : adjt[nodes[i]]) {
				if (ind[u] > i && (mn == -1 || ind[u] > ind[mn]))
						mn = u;
			}

			if (mn >= 0) adj[nodes[i]].push_back(mn), adj[mn].push_back(nodes[i]);
		}

		dfs1(1, 0);
	}

	if (*max_element(ans + 1, ans + n + 1) > 0) {
		for (int i = 1; i <= n; i++)
			if (ans[i] == 0)
				ans[i] = 3;

	}

	vector<int> res;
	for (int i = 1; i <= n; i++)
		res.push_back(T[ans[i]]);

	return res;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36