Submission #1222976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222976		AmirAli_H1	Simurgh (IOI17_simurgh)	C++17	100 / 100	85 ms	18960 KiB

simurgh

// In the name of Allah

#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 18) + 4;
const int limit = 8000;

int n, m, Qt;
vector<pii> adj[maxn];
vector<pii> E; int M[maxn];
int p[maxn], valx[maxn];
int mark[maxn], col[maxn], c;
vector<int> lsx[maxn], Ex, Rx, ans;
int valR[maxn]; vector<pii> resx;

int askx() {
	if (Qt + 1 > limit) exit(23);
	int x = count_common_roads(Ex); Qt++;
	return x;
}

int get(int a) {
	return (p[a] == a) ? a : p[a] = get(p[a]);
}

void merge(int a, int b) {
	a = get(a); b = get(b);
	if (a == b) return ;
	if (valx[a] != -1) valx[b] = valx[a];
	else if (valx[b] != -1) valx[a] = valx[b];
	p[a] = b;
}

void dfs(int v) {
	mark[v] = 1; col[v] = c;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) {
			Ex.pb(j);
			dfs(u);
		}
	}
}

void dfsx(int v, int p = -1) {
	bool okx = 0;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!M[u]) {
			okx = 1;
			break;
		}
	}
	if (!okx) return ;
	fill(mark, mark + n, 0);
	mark[v] = 1; c = 0; Ex.clear();
	for (int i = 0; i < n; i++) {
		if (!mark[i]) {
			lsx[c].clear(); dfs(i); c++;
		}
	}
	int vx = -1;
	vector<int> vc;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!M[u]) {
			lsx[col[u]].pb(j);
			vc.pb(u); M[u] = 1;
			Rx.pb(j);
		}
		else if (vx == -1 && u == p) {
			lsx[col[u]].pb(j); vx = u;
		}
	}
	for (int i = 0; i < c; i++) {
		Ex.pb(lsx[i].back());
	}
	for (int i = 0; i < c; i++) {
		Ex.erase(find(all(Ex), lsx[i].back()));
		for (int j = 0; j < len(lsx[i]); j++) {
			int x = lsx[i][j];
			Ex.pb(x); valR[j] = askx(); Ex.pop_back();
		}
		for (int j = 1; j < len(lsx[i]); j++) {
			int x1 = lsx[i][j - 1], x2 = lsx[i][j];
			int R1 = valR[j - 1], R2 = valR[j];
			if (R1 > R2) {
				valx[get(x1)] = 1; valx[get(x2)] = 0;
			}
			else if (R2 > R1) {
				valx[get(x2)] = 1; valx[get(x1)] = 0;
			}
			else {
				merge(x1, x2);
			}
		}
		Ex.pb(lsx[i].back());
		int x = lsx[i].back();
		if (valx[get(x)] == -1) valx[get(x)] = 1;
	}
	for (int u : vc) {
		dfsx(u, v);
	}
}

int oprx() {
	int R = 0;
	for (auto f : resx) {
		int jx = f.F; int ux = E[jx].F, vx = E[jx].S;
		if (get(ux) != get(vx)) {
			Ex.pb(jx); merge(ux, vx); R += f.S;
		}
	}
	return R;
}

int oprf(int v, int l, int r) {
	Ex.clear();
	iota(p, p + n, 0); fill(valx, valx + n, -1);
	for (int i = l; i < r; i++) {
		int j = adj[v][i].S;
		int u = E[j].F, v = E[j].S;
		Ex.pb(j); merge(u, v);
	}
	int R = oprx(); int res = askx() - R;
	return res;
}

void calx(int v, int l, int r, int R) {
	if (l >= r || R == 0) return ;
	if (R == r - l) {
		for (int i = l; i < r; i++) {
			int j = adj[v][i].S;
			ans.pb(j);
		}
		return ;
	}
	int mid = (l + r) / 2;
	int R1 = oprf(v, l, mid), R2 = R - R1;
	calx(v, l, mid, R1); calx(v, mid, r, R2);
}

vector<int> find_roads(int nx, vector<int> ux, vector<int> vx) {
	n = nx; m = len(ux);
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		if (u > v) swap(u, v);
		adj[u].pb(Mp(v, i)); adj[v].pb(Mp(u, i));
		E.pb(Mp(u, v));
	}
	iota(p, p + m, 0); fill(valx, valx + m, -1);
	fill(M, M + n, 0); M[0] = 1; dfsx(0);
	for (int j : Rx) resx.pb(Mp(j, valx[get(j)]));
	for (int i = 0; i < n; i++) adj[i].clear();
	for (int i = 0; i < m; i++) {
		int u = E[i].F, v = E[i].S;
		adj[u].pb(Mp(v, i));
	}
	for (int v = 0; v < n; v++) {
		calx(v, 0, len(adj[v]), oprf(v, 0, len(adj[v])));
	}
	return ans;
}

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