제출 #828114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828114		tranxuanbach	Simurgh (IOI17_simurgh)	C++17	51 / 100	87 ms	5496 KiB

simurgh

#include "simurgh.h"

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

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)a.size())

const int N = 5e2 + 5, M = N * (N - 1) / 2;

struct disjoint_set{
	int par[N];

	void reset(int n = N){
		fill(par, par + n, -1);
	}

	disjoint_set(){
		reset();
	}

	int root(int x){
		return (par[x] < 0 ? x : (par[x] = root(par[x])));
	}

	bool merge(int x, int y){
		if ((x = root(x)) == (y = root(y))){
			return false;
		}
		if (par[x] > par[y]){
			swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
		return true;
	}
} dsu;

struct weighted_disjoint_set{
	pair <int, int> par[M];

	void reset(int n = M){
		fill(par, par + n, pair{-1, 0});
	}

	weighted_disjoint_set(){
		reset();
	}

	pair <int, int> root(int x){
		if (par[x].fi < 0){
			return pair{x, 0};
		}
		pair <int, int> ans = root(par[x].fi);
		ans.se ^= par[x].se;
		return (par[x] = ans);
	}

	bool share(int x, int y){
		return (root(x).fi == root(y).fi);
	}

	int dist(int x, int y){
		return (root(x).se ^ root(y).se);
	}

	bool merge(int x, int y, int val){
		auto [tx, vx] = root(x);
		auto [ty, vy] = root(y);
		if (tx == ty){
			return false;
		}
		val ^= vx ^ vy;
		if (par[tx].fi > par[ty].fi){
			swap(tx, ty);
		}
		par[tx].fi += par[ty].fi;
		par[ty] = pair{tx, val};
		return true;
	}
} wdsu;

int n, m;
pair <int, int> edge[M];
int adj[N][N];
vector <int> vadj[N];

vector <int> find_spanning_tree(){
	vector <int> ans;
	For(i, 0, m){
		auto [u, v] = edge[i];
		if (dsu.merge(u, v)){
			ans.emplace_back(i);
		}
	}
	return ans;
}

namespace subtask123{
	bool check(){
		return n <= 240;
	}

	int msk[N];
	vector <int> vadj_tree[N];
	int known_edge[M];

	void dfs_msk(int u, int p, int val){
		msk[u] = val;
		for (auto v: vadj_tree[u]){
			if (v == p){
				continue;
			}
			dfs_msk(v, u, val);
		}
	}

	vector <int> solve(){
		vector <int> mst = find_spanning_tree();
		// cout << "mst" << endl;
		// for (auto i: mst){
		// 	cout << i << ' ';
		// }
		// cout << endl;
		int count_mst = count_common_roads(mst);
		for (auto i: mst){
			auto &[u, v] = edge[i];
			vadj_tree[u].emplace_back(v);
			vadj_tree[v].emplace_back(u);
		}
		fill(known_edge, known_edge + m, -1);

		for (auto id: mst){
			vector <int> rem_mst;
			for (auto i: mst){
				if (i != id){
					rem_mst.emplace_back(i);
				}
			}
			auto query = [&](int i){
				rem_mst.emplace_back(i);
				int ans = count_common_roads(rem_mst);
				rem_mst.pop_back();
				return ans;
			};

			auto &[s, t] = edge[id];
			dfs_msk(s, t, s);
			dfs_msk(t, s, t);
			// cout << "id " << id << endl;
			// For(u, 0, n){
			// 	cout << msk[u] << ' ';
			// }
			// cout << endl;

			For(i, 0, m){
				if (i == id){
					continue;
				}
				auto &[u, v] = edge[i];
				if (msk[u] == msk[v]){
					continue;
				}
				if (wdsu.share(i, id)){
					// cout << "share " << id << ' ' << i << ' ' << wdsu.dist(i, id) << endl;
					if (known_edge[id] == -1 and wdsu.dist(i, id)){
						int cur = query(i);
						if (cur < count_mst){
							known_edge[id] = 1;
						}
						else{
							known_edge[id] = 0;
						}
					}
					continue;
				}
				// cout << "new connection " << id << ' ' << i << endl;
				int cur = query(i);
				// cout << cur << ' ' << count_mst << endl;
				if (cur < count_mst){
					known_edge[id] = 1;
					wdsu.merge(i, id, 1);
				}
				else if (cur > count_mst){
					known_edge[id] = 0;
					wdsu.merge(i, id, 1);
				}
				else{
					wdsu.merge(i, id, 0);
				}
			}
			if (known_edge[id] == -1){
				known_edge[id] = 1;
			}
			// cout << "known_edge " << id << ' ' << known_edge[id] << endl;
		}
		For(i, 0, m){
			if (known_edge[i] != -1){
				auto [j, w] = wdsu.root(i);
				known_edge[j] = known_edge[i] ^ w;
			}
		}
		For(i, 0, m){
			if (known_edge[i] == -1){
				auto [j, w] = wdsu.root(i);
				known_edge[i] = known_edge[j] ^ w;
			}
		}
		vector <int> ans;
		For(i, 0, m){
			if (known_edge[i]){
				ans.emplace_back(i);
			}
		}
		return ans;
	}
}

vector <int> find_roads(int _n, vector <int> _u, vector <int> _v){
	n = _n;
	m = isz(_u);
	For(u, 0, n){
		For(v, 0, n){
			adj[u][v] = -1;
		}
	}
	For(i, 0, m){
		int u = _u[i], v = _v[i];
		edge[i] = pair{u, v};
		adj[u][v] = adj[v][u] = i;
		vadj[u].emplace_back(i);
		vadj[v].emplace_back(i);
	}

	if (subtask123::check()){
		return subtask123::solve();
	}
	return {};
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30