Submission #1209057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209057		abczz	Simurgh (IOI17_simurgh)	C++20	0 / 100	167 ms	7976 KiB

simurgh

#include "simurgh.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll W[250000];
ll N, z, D[500], X[500], Y[500], P[500], E[500], dsuP[500];
vector <array<ll, 3>> Z;
vector <array<ll, 2> > adj[500];
void dfs(ll u, ll w) {
	D[u] = w;
	for (auto [v, x] : adj[u]) {
		if (D[v] == -1) {
			P[v] = u, E[v] = x;
			dfs(v, w+1);
		}
		else if (D[v] < D[u]-1 && D[v] < X[u]) {
			X[u] = D[v], Y[u] = x;
		}
	}
}
ll query(ll x, ll y) {
	vector <int> Q;
	for (auto [u, a, b] : Z) {
		if (u == x) Q.push_back(y);
		else Q.push_back(u);
	}
	return count_common_roads(Q);
}
ll dsu(ll u) {
	if (dsuP[u] == u) return u;
	else return dsuP[u] = dsu(dsuP[u]);
}
ll bsquery(ll u, vector <array<ll, 2>> V) {
	for (int i=0; i<N; ++i) dsuP[i] = i;
	vector <int> Q;
	ll w = 0;
	for (auto [x, y] : V) {
		ll a = dsu(u), b = dsu(x);
		dsuP[a] = b;
		Q.push_back(y);
	}
	for (auto [y, a, b] : Z) {
		a = dsu(a), b = dsu(b);
		if (a != b) {
			dsuP[a] = b;
			Q.push_back(y);
			w += W[y];
		}
	}
	return count_common_roads(Q) - w;
}
void solve(ll u) {
	if (X[u] != 1e18) {
		vector <array<ll, 2> > V;
		ll v = u;
		while (D[v] != X[u] && W[E[v]] == -1) {
			V.push_back({E[v], 0});
			v = P[v];
		}
		for (int i=0; i<V.size(); ++i) {
			V[i][1] = query(V[i][0], Y[u]);
		}
		V.push_back({Y[u], z});
		sort(V.begin(), V.end(), [](auto a, auto b) {
			return a[1] > b[1];
		});
		if (V[0][1] == V.back()[1]) {
			for (auto [x, y] : V) W[x] = 0;
		}
		else {
			for (int i=0; i<V.size(); ++i) {
				if (V[i][1] != V.back()[1]) W[V[i][0]] = 0;
				else W[V[i][0]] = 1;
			}
		}
	}
	for (auto [v, x] : adj[u]) {
		if (D[v] != D[u]+1) continue;
		solve(v);
	}
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N = n;
	for (int i=0; i<n; ++i) D[i] = -1, X[i] = 1e18;
	for (int i=0; i<u.size(); ++i) {
		W[i] = -1;
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
	}
	P[0] = -1;
	dfs(0, 0);
	for (int i=1; i<n; ++i) Z.push_back({E[i], i, P[i]});
	z = query(-1, -1);
	solve(0);
	for (int i=1; i<n; ++i) {
		if (W[E[i]] == -1) W[E[i]] = 1;
	}
	vector <int> F;
	for (int i=0; i<n; ++i) {
		vector <array<ll, 2> > V;
		for (auto [x, y] : adj[i]) {
			if (i < x) V.push_back({x, y});
		}
		while (!V.empty()) {
			if (!bsquery(i, V)) break;
			ll l = 0, r = (ll)V.size()-1, mid;
			while (l < r) {
				mid = (l+r)/2;
				vector <array<ll, 2>> tmp;
				for (int j=l; j<=mid; ++j) tmp.push_back(V[j]);
				if (bsquery(i, tmp)) r = mid;
				else l = mid+1;
			}
			F.push_back(V[l][1]);
			swap(V[l], V[(ll)V.size()-1]);
			V.pop_back();
		}
	}
	return F;
}

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