제출 #1227567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227567		The_Samurai	Simurgh (IOI17_simurgh)	C++20	13 / 100	14 ms	7864 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
mt19937 rng(213124);

int rand(int l, int r) {
	int x = rng();
	return abs(x) % (r - l + 1) + l;
}

struct dsu {
	vector<vector<int>> childs;
	vector<int> par;

	void init(int n) {
		childs.assign(n, {});
		par.assign(n, 0);
		for (int i = 0; i < n; i++) par[i] = i, childs[i].emplace_back(i);
	}

	int get(int a) { return par[a]; }

	void merge(int a, int b) {
		if (par[a] == par[b]) return;
		a = par[a]; b = par[b];
		if (childs[a].size() < childs[b].size()) swap(a, b);
		for (int x: childs[b]) {
			par[x] = a;
			childs[a].emplace_back(x);
		}
		childs[b].clear();
	}
};

std::vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
	vector<pair<int, int>> all;
	for (int i = 0; i < U.size(); i++) all.emplace_back(min(U[i], V[i]), max(U[i], V[i]));
	vector gold(n, vector(n, -1));
	dsu edge; edge.init(U.size());
	vector vis(U.size(), false);
	while (true) {
		dsu ds; ds.init(n);
		vector<int> used;
		vector now(n + 1, false);
		for (int i = 0; i < all.size(); i++) {
			if (gold[all[i].ff][all[i].ss] == 1) {
				vis[i] = true;
				used.emplace_back(i);
				ds.merge(all[i].ff, all[i].ss);
			}
		}
		vector<int> ord(all.size());
		iota(ord.begin(), ord.end(), 0);
		for (int i = 0; i < ord.size(); i++) swap(ord[i], ord[rand(0, i)]);
		for (int i = 0; i < all.size(); i++) {
			auto [u, v] = all[ord[i]];
			if (gold[u][v] == 0) continue;
			if (ds.get(u) == ds.get(v)) continue;
			ds.merge(u, v);
			now[ord[i]] = true;
			used.emplace_back(ord[i]);
		}
		// for (int x: used) cout << x << ' ';
		// cout << endl;
		int old = count_common_roads(used);
		if (old == n - 1) {
			return used;
		}
		// for (int i = 0; i < n - 1; i++) swap(used[i], used[rand(0, i)]);
		// for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
		// 	if (gold[i][j] != -1) {
		// 		cout << i << ' ' << j << ' ' << gold[i][j] << endl;
		// 	}
		// }
		for (int i = 0; i < U.size(); i++) {
			if (vis[i] or now[i]) continue;
			vis[i] = true;
			ds.init(n);
			ds.merge(all[i].ff, all[i].ss);
			bool bad = false;
			vector<int> shit = {i};
			int wh;
			for (int j: used) {
				auto [u, v] = all[j];
				if (ds.get(u) == ds.get(v) and gold[u][v] == 1) bad = true;
				if (ds.get(u) != ds.get(v)) shit.emplace_back(j);
				else wh = j;
				ds.merge(u, v);
			}
			if (bad) {
				gold[all[i].ff][all[i].ss] = gold[all[i].ss][all[i].ff] = 0;
				continue;
			}
			int nw = count_common_roads(shit);
			// cout << i << ' ' << wh << ' ' << old << ' ' << nw << endl;
			if (old == nw) {
				edge.merge(i, wh);
			} else if (old + 1 == nw) {
				for (int x: edge.childs[edge.get(i)]) {
					auto [u, v] = all[x];
					gold[u][v] = gold[v][u] = 1;
				}
				for (int x: edge.childs[edge.get(wh)]) {
					auto [u, v] = all[x];
					gold[u][v] = gold[v][u] = 0;
				}
			} else if (old - 1 == nw) {
				for (int x: edge.childs[edge.get(i)]) {
					auto [u, v] = all[x];
					gold[u][v] = gold[v][u] = 0;
				}
				for (int x: edge.childs[edge.get(wh)]) {
					auto [u, v] = all[x];
					gold[u][v] = gold[v][u] = 1;
				}
			}
			break;
		}
	}
}

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