Submission #1205293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205293		Szil	Simurgh (IOI17_simurgh)	C++20	100 / 100	1010 ms	6484 KiB

simurgh

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

using namespace std;

struct dsu {
	vector<int> par;

	dsu(int n) {
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}

	int holvan(int u) {
		return par[u] == u ? u : (par[u] = holvan(par[u]));
	}

	bool unio(int u, int v) {
		u = holvan(u); v = holvan(v);
		if (u == v) return 0;
		par[u] = v;
		return 1;
	}
};

vector<int> find_roads(int n, vector<int> e1, vector<int> e2) {
	int m = e1.size();
	vector<vector<pair<int, int>>> g(n), g2(n);
	vector<int> dfs_tree;
	vector<int> col(n);
	vector<bool> vis(n);
	for (int i = 0; i < m; i++) {
		g[e1[i]].emplace_back(e2[i], i);
		g[e2[i]].emplace_back(e1[i], i);
	}
	auto dfs = [&](auto &&self, int u) -> void {
		vis[u] = 1;
		for (auto [v, idx] : g[u]) {
			if (vis[v]) continue;
			dfs_tree.emplace_back(idx);
			g2[u].emplace_back(v, idx);
			g2[v].emplace_back(u, idx);
			self(self, v);
		}
	};
	dfs(dfs, 0);
	auto dfs2 = [&](auto &&self, int u, int block, int c) -> void {
		col[u] = c;
		for (auto [v, idx] : g2[u]) {
			if (col[v] || v == block) continue;
			self(self, v, block, c);
		}
	};

	int asked = 0;
	int dfs_tree_cnt = count_common_roads(dfs_tree);
	asked++;
	vector<int> label(m, -1);
	for (int idx : dfs_tree) {
		int u = e1[idx];
		int v = e2[idx];
		fill(col.begin(), col.end(), 0);
		dfs2(dfs2, u, v, 1);
		dfs2(dfs2, v, u, 2);
		vector<int> replacements;
		for (int i = 0; i < m; i++) {
			if (i == idx) continue;
			if (col[e1[i]] != col[e2[i]]) {
				replacements.emplace_back(i);
			}
		}
		if (replacements.empty()) {
			label[idx] = 1;
			continue;
		}
		vector<int> s;
		for (int x : dfs_tree) {
			if (x != idx) s.emplace_back(x);
		}
		bool ok = false;
		for (int x : replacements) {
			if (label[x] != -1) {
				s.emplace_back(x);
				ok = true;
				assert(asked <= 8000);
				int cnt = count_common_roads(s);
				asked++;
				int should_be = dfs_tree_cnt + (label[x] == 1);
				label[idx] = should_be != cnt;
				break;
			}
		}

		if (ok) continue;
		
		label[idx] = 1;
		int it = 0;
		vector<int> checked;
		for (int x : replacements) {
			it++;
			s.emplace_back(x);
			assert(asked <= 8000);
			int cnt = count_common_roads(s);
			asked++;
			if (cnt > dfs_tree_cnt) {
				label[idx] = 0;
				break;
			}
			if (cnt < dfs_tree_cnt) {
				break;
			}
			checked.emplace_back(x);
			s.pop_back();
		}
		for (int x : checked) {
			label[x] = label[idx];
		}
	}

	vector<int> todo;
	vector<int> vis2(n), vis3(m);
	
	auto gen_todo = [&](auto &&self, int u) -> void {
		vis2[u] = 1;
		for (auto [v, idx] : g[u]) {
			if (label[idx] != -1 || vis2[v] || vis3[idx]) continue;
			vis3[idx] = 1;
			todo.emplace_back(idx);
			self(self, v);
		}
	};
	for (int it = 0; it < 500; it++) {
		fill(vis2.begin(), vis2.end(), 0);
		for (int i = 0; i < n; i++) {
			if (!vis2[i]) gen_todo(gen_todo, i);
		}
	}

	auto f = [&](int l, int r) {
		dsu ds(n);
		vector<int> roads;
		for (int i = l; i < r; i++) {
			ds.unio(e1[todo[i]], e2[todo[i]]);
			roads.emplace_back(todo[i]);
		}
		int should_be = dfs_tree_cnt;
		for (int idx : dfs_tree) {
			if (!ds.unio(e1[idx], e2[idx])) {
				should_be -= label[idx];
			} else {
				roads.emplace_back(idx);
			}
		}
		int cnt = count_common_roads(roads);
		asked++;
		return cnt > should_be;
	};

	int nxt = 0;
	while (nxt < todo.size()) {
		int last = nxt;
		dsu ds(n);
		while (last < todo.size()) {
			if (ds.unio(e1[todo[last]], e2[todo[last]])) {
				last++;
			} else {
				break;
			}
		}
		if (!f(nxt, last)) {
			nxt = last;
			continue;
		}
		int lo = nxt, hi = last-1;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (!f(nxt, mid)) lo = mid;
			else hi = mid-1;
		}
		nxt = lo+1;
		label[todo[lo]] = 1;
	}

	vector<int> ans;
	for (int i = 0; i < m; i++) {
		if (label[i] == 1) ans.emplace_back(i);
	}
	
	return ans;
}

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