Submission #1147719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147719		gyg	Simurgh (IOI17_simurgh)	C++20	51 / 100	1049 ms	126508 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second 
const int N = 5e3 + 5;

int n, m;
arr<vec<int>, N> adj;
map<int, pii> edg;
map<pii, int> id;

vec<int> spn, bck;
arr<bool, N> vs;
arr<int, N> pr, dpt;
void dfs(int u = 0) {
	vs[u] = true;
	for (int v : adj[u]) {
		if (vs[v]) {
			if (v == pr[u]) continue;
			if (dpt[v] < dpt[u]) bck.push_back(id[{u, v}]);
		} else {
			pr[v] = u, dpt[v] = dpt[u] + 1;
			spn.push_back(id[{u, v}]);
			dfs(v);
		}
	}
}

map<int, vec<int>> ovr;
void ovr_cmp() {
	for (int i : bck) {
		int u = edg[i].fir, v = edg[i].sec;
		if (dpt[u] > dpt[v]) swap(u, v);
		while (v != u) {
			ovr[id[{v, pr[v]}]].push_back(i);
			v = pr[v];
		}
	}
}

int qry(vec<int> x) {
	vec<sig> y;
	y.insert(y.end(), x.begin(), x.end());
	return count_common_roads(y);
}

map<int, int> on;
void on_cmp() {
	for (int i = 0; i < m; i++) on[i] = -1;

	for (int i : spn) {
		vec<int> bs = spn;
		bs.erase(find(bs.begin(), bs.end(), i));

		vec<int> lst = {i};
		bool flg = false;
		for (int j : ovr[i]) {
			if (!flg && on[j] == 1) lst.push_back(j), flg = true;
			if (on[j] == -1) lst.push_back(j);
		}

		int mx = -1;
		map<int, int> rsp;
		for (int j : lst) {
			bs.push_back(j);
			rsp[j] = qry(bs);
			mx = max(mx, rsp[j]);
			bs.pop_back();
		}
		for (int j : lst) {
			if (rsp[j] == mx) on[j] = 1;
			else on[j] = 0;
		}

		// cout << i << ": " << mx.fir << " " << mx.sec << endl;
		// for (int j : lst) cout << j << " ";
		// cout << endl;
	}
}

vec<sig> find_roads(sig _n, vec<sig> _u, vec<sig> _v) {
	n = _n, m = _u.size();
	for (int i = 0; i < m; i++) {
		adj[_u[i]].push_back(_v[i]), adj[_v[i]].push_back(_u[i]);
		edg[i] = {_u[i], _v[i]};
		id[{_u[i], _v[i]}] = id[{_v[i], _u[i]}] = i;
	}
	
	dfs();
	ovr_cmp();
	on_cmp();

	// for (int x : spn) cout << x << " ";
	// cout << endl;
	// for (int x : bck) cout << x << " ";
	// cout << endl;
	// for (pair<int, vec<int>> x : ovr) {
	// 	cout << x.fir << ": ";
	// 	for (int y : x.sec) cout << y << " ";
	// 	cout << endl;
	// }

	// for (int i = 0; i < m; i++) {
	// 	cout << i << ": " << on[i] << endl;
	// }

	vec<sig> ans;
	for (int i = 0; i < m; i++)
		if (on[i] == 1) ans.push_back(i);
	assert(ans.size() == n - 1);
	return ans;
}

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