Submission #851861

#	Time	Username	Problem	Language	Result	Execution time	Memory
851861		mickey080929	Simurgh (IOI17_simurgh)	C++17	100 / 100	100 ms	8264 KiB

simurgh

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

using namespace std;
typedef pair<int,int> pii;

const int inf = 1e9;

int ori;
vector<vector<pii>> adj;
vector<vector<pii>> back_edges;
vector<vector<pii>> childs;
vector<int> color; // -1 : uncolored, 0 : normal edge, 1 : golden edge
vector<int> vis;
vector<pii> par;
vector<int> dep;
vector<int> query;
vector<int> ans;

int ask() { return count_common_roads(query); }

void ins(vector<int> v) {
	for (auto &i : v)
		query.push_back(i);
}

vector<int> chk;
void del(vector<int> v) {
	for (auto &i : v) chk[i] = 1;
	vector<int> t;
	for (auto &i : query)
		if (!chk[i])
			t.push_back(i);
	query = t;
	for (auto &i : v) chk[i] = 0;
}

void make_dfs_tree(int x) {
	vis[x] = 1;
	for (auto &[y, id] : adj[x]) {
		if (y == par[x].first) continue;
		if (vis[y]) {
			back_edges[x].emplace_back(y, id);
			continue;
		}
	}
	for (auto &[y, id] : adj[x]) {
		if (vis[y]) continue;
		childs[x].emplace_back(y, id);
		par[y] = make_pair(x, id);
		dep[y] = dep[x] + 1;
		make_dfs_tree(y);
	}
}

void color_dfs_tree(int x) {
	if (!back_edges.empty()) {
		int mn = inf;
		pii e;
		for (auto &[y, id] : back_edges[x]) {
			if (mn > dep[y]) {
				mn = dep[y];
				e = make_pair(y, id);
			}
		}
		if (mn < inf) {
			vector<int> path;
			int t = x;
			int oth = -1;
			while (t != e.first) {
				if (color[par[t].second] == -1)
					path.push_back(par[t].second);
				else
					oth = par[t].second;
				t = par[t].first;
			}
			if (!path.empty()) {
				vector<int> ret(path.size());
				ins({e.second});
				for (int i=0; i<(int)path.size(); i++) {
					del({path[i]});
					ret[i] = ask();
					ins({path[i]});
				}
				del({e.second});
				int d = 0;
				if (oth == -1) {
					for (int i=0; i<(int)path.size(); i++) {
						if (ret[i] > ori) d = 1;
					}
				}
				else {
					ins({e.second});
					del({oth});
					d = ask() > ori-color[oth] ? 1 : 0;
					del({e.second});
					ins({oth});
				}
				for (int i=0; i<(int)path.size(); i++) {
					color[path[i]] = ret[i]-d < ori ? 1 : 0;
				}
			}
		}
	}
	for (auto &[y, id] : childs[x]) {
		color_dfs_tree(y);
	}
}

void color_back_edges(int x) {
	if (!back_edges.empty()) {
		sort(back_edges[x].begin(), back_edges[x].end(), [&] (pii u, pii v) { return dep[u.first] > dep[v.first]; });
		vector<int> er(back_edges[x].size());
		int idx = 0;
		int t = x;
		while (t > 0) {
			if (idx < (int)back_edges[x].size() && par[t].first == back_edges[x][idx].first) {
				er[idx] = par[t].second;
				idx ++;
			}
			t = par[t].first;
		}
		int p = 0;
		while (true) {
			int lo = p, hi = (int)back_edges[x].size();
			while (lo < hi) {
				int mid = lo + hi >> 1;
				int d = 0;
				vector<int> t1, t2;
				for (int i=p; i<=mid; i++) {
					t1.push_back(back_edges[x][i].second);
					t2.push_back(er[i]);
					d += color[er[i]];
				}
				ins(t1);
				del(t2);
				if (ori - d < ask()) hi = mid;
				else lo = mid + 1;
				del(t1);
				ins(t2);
			}
			if (lo == (int)back_edges[x].size()) break;
			ans.push_back(back_edges[x][lo].second);
			p = lo + 1;
		}
	}
	for (auto &[y, id] : childs[x]) {
		color_back_edges(y);
	}
}

void init(int n, int m) {
	adj.resize(n, vector<pii>());
	back_edges.resize(n, vector<pii>());
	childs.resize(n, vector<pii>());
	color.resize(m, -1);
	vis.resize(n, 0);
	par.resize(n);
	dep.resize(n);
	chk.resize(m, 0);
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = (int) u.size();
	init(n, m);
	for (int i=0; i<m; i++) {
		adj[u[i]].emplace_back(v[i], i);
		adj[v[i]].emplace_back(u[i], i);
	}
	par[0] = make_pair(-1,-1);
	dep[0] = 0;
	make_dfs_tree(0);
	for (int i=1; i<n; i++) query.push_back(par[i].second);
	ori = ask();
	color_dfs_tree(0);
	for (int i=1; i<n; i++) {
		if (color[par[i].second] == -1) color[par[i].second] = 1;
		if (color[par[i].second] == 1) ans.push_back(par[i].second);
	}
	color_back_edges(0);
	assert((int)ans.size() == n-1);

	return ans;
}

Compilation message (stderr)

simurgh.cpp: In function 'void color_back_edges(int)':
simurgh.cpp:127:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     int mid = lo + hi >> 1;
      |               ~~~^~~~

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