Submission #51940

#	Time	Username	Problem	Language	Result	Execution time	Memory
51940		aome	Simurgh (IOI17_simurgh)	C++17	100 / 100	407 ms	20632 KiB

simurgh

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

using namespace std;

const int N = 510;
const int M = 510 * 510 / 2;

int n, m;
int pset[N];
int deg[N];
int label[N][N];
int par[N], h[N];
int visit_edge[M];
bool visit[N];
vector<int> G[N];
vector<int> vtree;

int find(int u) { 
	return u == pset[u] ? u : pset[u] = find(pset[u]); 
}

bool join(int u, int v) {
	u = find(u), v = find(v), pset[u] = v; return u != v;
}

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (visit[v]) continue;
		vtree.push_back(label[u][v]);
		par[v] = u, h[v] = h[u] + 1, dfs(v);
	}
}


vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
	n = _n, m = u.size();
	for (int i = 0; i < m; ++i) {
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
		label[u[i]][v[i]] = label[v[i]][u[i]] = i;
	}
	dfs(0);
	int val = count_common_roads(vtree);
	for (int i = 0; i < m; ++i) {
		if (h[u[i]] > h[v[i]]) swap(u[i], v[i]);
		int cur = v[i];
		vector<int> vec;
		while (cur != u[i]) {
			int tmp = cur; cur = par[cur];
			vec.push_back(label[cur][tmp]);
		}
		bool flag = 0;
		for (auto j : vec) flag |= !visit_edge[j];
		if (!flag || vec.size() == 1) continue;
		int id = -1;
		for (auto j : vec) if (visit_edge[j]) id = j;
		if (id == -1) {
			for (auto j : vec) {
				vector<int> ask = vtree;
				for (auto &k : ask) if (k == j) k = i;
				int tmp = count_common_roads(ask);
				if (tmp != val) {
					visit_edge[i] = (tmp > val) + 1;
					visit_edge[j] = 3 ^ visit_edge[i];
					// 1 : not loyal, 2 : loyal
				}
			}
			if (!visit_edge[i]) visit_edge[i] = 1;
			for (auto j : vec) {
				if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
			}
		}
		else {
			vector<int> ask = vtree;
			for (auto &j : ask) if (j == id) j = i;
			int tmp = count_common_roads(ask);
			if (tmp == val) visit_edge[i] = visit_edge[id];
			else visit_edge[i] = 3 ^ visit_edge[id];
			for (auto j : vec) {
				if (!visit_edge[j]) {
					vector<int> ask = vtree;
					for (auto &k : ask) if (k == j) k = i;
					int tmp = count_common_roads(ask);
					if (tmp == val) visit_edge[j] = visit_edge[i];
					else visit_edge[j] = 3 ^ visit_edge[i];
				}
			} 
		}
	}
	for (auto i : vtree) {
		if (!visit_edge[i]) visit_edge[i] = 2;
	}
	// for (auto i : vtree) cout << i << ' '; cout << '\n';
	// for (auto i : vtree) cout << visit_edge[i] << ' '; cout << '\n';
	queue<int> qu;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) pset[j] = j;
		vector<int> ask;
		int cnt = 0;
		for (auto j : G[i]) {
			int tmp = label[i][j];
			join(i, j), ask.push_back(tmp), cnt += visit_edge[tmp] == 2;
		}
		for (auto j : vtree) {
			if (join(u[j], v[j])) {
				cnt += visit_edge[j] == 2, ask.push_back(j);
			}
		}
		deg[i] = count_common_roads(ask) - cnt;
		if (deg[i] == 1) qu.push(i);
	}
	// for (int i = 0; i < m; ++i) cout << visit_edge[i] << ' '; cout << '\n'; 
	// for (int i = 0; i < n; ++i) cout << deg[i] << ' '; cout << '\n';
	while (qu.size()) {
		int x = qu.front(); qu.pop();
		if (deg[x] != 1) continue;
		vector<int> vec;
		for (auto i : G[x]) {
			if (!visit_edge[label[x][i]]) {
				vec.push_back(label[x][i]);
			}
		}
		int l = 0, r = vec.size();
		while (l < r) {
			int mid = (l + r) >> 1;
			for (int i = 0; i < n; ++i) pset[i] = i;
			vector<int> ask;
			int cnt = 0;
			for (int i = l; i <= mid; ++i) {
				int tmp = vec[i];
				join(u[tmp], v[tmp]);
				ask.push_back(tmp);
				cnt += visit_edge[tmp] == 2;
			}
			for (auto i : vtree) {
				if (join(u[i], v[i])) {
					ask.push_back(i);
					cnt += visit_edge[i] == 2;
				}
			}
			int tmp = count_common_roads(ask);
			if (tmp == cnt + 1) r = mid;
			else l = mid + 1;
		}
		visit_edge[vec[l]] = 2;
		int y = u[vec[l]];
		if (x == y) y = v[vec[l]];
		deg[y]--;
		if (deg[y] == 1) qu.push(y);
	}
	vector<int> res;
	for (int i = 0; i < m; ++i) {
		if (visit_edge[i] == 2) res.push_back(i);
	}
	return res;
}

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