제출 #1227532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227532		The_Samurai	Simurgh (IOI17_simurgh)	C++20	0 / 100	82 ms	7608 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());
	while (true) {
		dsu ds; ds.init(n);
		vector<int> used;
		for (int i = 0; i < all.size(); i++) {
			if (gold[all[i].ff][all[i].ss] == 1) {
				used.emplace_back(i);
				ds.merge(all[i].ff, all[i].ss);
			}
		}
		for (int i = 0; i < all.size(); i++) {
			if (ds.get(all[i].ff) == ds.get(all[i].ss)) continue;
			ds.merge(all[i].ff, all[i].ss);
			used.emplace_back(i);
		}
		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 x: used) cout << x << ' ';
		// cout << endl;
		// 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 < n - 1; i++) {
			if (gold[all[used[i]].ff][all[used[i]].ss] == 1) continue;
			ds.init(n + 1);
			for (int j: used) {
				if (used[i] == j) continue;
				ds.merge(all[j].ff, all[j].ss);
			}
			// cout << i << endl;
			
			int old_val = used[i];
			bool found = false;
			int cnt = 0;
			for (int j = 0; j < all.size() and !found; j++) {
				auto [u, v] = all[j];
				// cout << j << ' ' << u << ' ' << v << endl;
				if (gold[u][v] != -1) continue;
				if (ds.get(u) == ds.get(v) or used[i] == j) continue;
				if (edge.get(u) == edge.get(v)) continue;
				used[i] = j;
				cnt++;
				int nw = count_common_roads(used);
				if (old == nw) {
					edge.merge(j, old_val);
				} else if (old + 1 == nw) {
					for (int x: edge.childs[edge.get(j)]) {
						auto [u, v] = all[x];
						gold[u][v] = gold[v][u] = 1;
					}
					for (int x: edge.childs[edge.get(old_val)]) {
						auto [u, v] = all[x];
						gold[u][v] = gold[v][u] = 0;
					}
					found = true;
				} else if (old - 1 == nw) {
					for (int x: edge.childs[edge.get(j)]) {
						auto [u, v] = all[x];
						gold[u][v] = gold[v][u] = 0;
					}
					for (int x: edge.childs[edge.get(old_val)]) {
						auto [u, v] = all[x];
						gold[u][v] = gold[v][u] = 1;
					}
					used[i] = old_val;
					found = true;
				}
			}
			if (cnt == 0) {
				auto [u, v] = all[old_val];
				gold[u][v] = gold[v][u] = 1;
				break;
			}
			if (found) break;
		}
	}
}

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