Submission #742727

#	Time	Username	Problem	Language	Result	Execution time	Memory
742727		sidon	Simurgh (IOI17_simurgh)	C++17	100 / 100	384 ms	8260 KiB

simurgh

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

struct UFDS {
	vector<int> e;
	int operator()(int u) {
		return e[u] < 0 ? u : e[u] = (*this)(e[u]);
	}
	bool operator()(int u, int v) {
		if((u = (*this)(u)) == (v = (*this)(v))) return false;
		if(e[u] > e[v]) swap(u, v);
		e[u] += e[v], e[v] = u;
		return true;
	}
	UFDS(int n) { e.assign(n, -1); }
};

const int Z = 500, NE = Z * Z / 2;

int vis[Z], visE[NE], t[NE], over[NE];
vector<int> st;
vector<array<int, 2>> g[Z], s, h[NE], q;
vector<array<int, 3>> o;

int ask(int u, int v) {
	for(int &j : st) if(j == u) j = v;
	int res = count_common_roads(st);
	for(int &j : st) if(j == v) j = u;

	return res;
}

void dfs(int u, int p) {
	vis[u] = 1;
	for(auto [v, i] : g[u]) if(v != p) {
		if(vis[v] == 1) {
			for(int j = size(s); j--; ) {
				over[s[j][1]] = i;
				t[s[j][1]] = -1;
				if(s[j][0] == v) break;
				if(!visE[s[j][1]]++) o.pb({s[j][1], s[j-1][1], i});
			}
		} else if(!vis[v]) {
			s.pb({u, i});
			st.pb(i);
			t[i] = 1;
			dfs(v, u);
			s.pop_back();
		}
	}
	vis[u] = 2;
}

void color(int u) {
	for(auto [v, w] : h[u]) if(t[v] < 0) {
		t[v] = t[u] ^ w;
		color(v);
	}
}

vector<int> find_roads(int n, vector<int> U, vector<int> V) {
	for(int i = size(U); i--; ) {
		g[U[i]].pb({V[i], i});
		g[V[i]].pb({U[i], i});
	}

	fill(t, t + NE, -1);
	dfs(0, 0);

	int def = count_common_roads(st);

	for(auto [a, b, i] : o) {	
		int x = ask(a, i), y = ask(b, i);

		h[b].pb({a, x != y});
		h[a].pb({b, x != y});

		if(x != y) q.pb({a, x < y});
	}

	while(1) {
		for(auto [u, w] : q) if(t[u] < 0) {
			t[u] = w;
			color(u);
		}
		q.clear();

		bool done = 1;
		for(int i : st) if(t[i] < 0) {
			int e = over[i];
			done = 0;

			q.pb({i, ask(i, e) < def});
		} 
		if(done) break;
	}

	for(int u = 0; u < n; ++u) {
		vector<int> a;
		for(auto [v, i] : g[u]) if(u < v && t[i] < 0)
			a.pb(i);

		while(!empty(a)) {
			int x = 0;
			for(int y = 1<<10; y /= 2; ) if(x + y <= (int)size(a)) {
				x += y;

				UFDS uf(n);
				vector<int> qry;
				for(int i = 0; i < x; ++i) {
					uf(U[a[i]], V[a[i]]);
					qry.pb(a[i]);
				}

				int cnt {};
				for(int e : st) if(uf(U[e], V[e])) {
					qry.pb(e);
					cnt += t[e];
				}

				if(cnt < count_common_roads(qry)) x -= y;
			}
			for(int i = 0; i < x; ++i)
				t[a[i]] = 0;
			if(x == (int)size(a)) break;
			t[a[x]] = 1;
			a = vector<int> {begin(a) + x + 1, end(a)};			
		}
	}

	vector<int> res;
	for(int i = size(U); i--; )
		if(t[i] == 1) res.pb(i);
	return res;
}

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