제출 #742722

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742722		sidon	Simurgh (IOI17_simurgh)	C++17	100 / 100	1320 ms	137432 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
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) {
		u = (*this)(u), v = (*this)(v);
		if(u == 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[NE], t[NE], backedgeFrom[NE];
vector<int> st;
vector<array<int, 2>> g[Z], s, h[NE], q;
map<int, vector<int>> backedges;

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--; ) {
				backedges[i].push_back(s[j][1]);
				backedgeFrom[s[j][1]] = i;
				t[s[j][1]] = -1;
				if(s[j][0] == v) break;
			}
		} else if(!vis[v]) {
			s.push_back({u, i});
			st.push_back(i);
			t[i] = 1;
			dfs(v, u);
			s.pop_back();
		}
	}
	vis[u] = 2;
}

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 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]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}

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

	fill(vis, vis + n, 0);

	int def = count_common_roads(st);
	for(auto [e, c] : backedges) {
		for(int i = size(c); --i; ) if(!vis[c[i-1]]++) {
			int x = ask(c[i-1], e), y = ask(c[i], e);

			h[c[i]].push_back({c[i-1], x != y});
			h[c[i-1]].push_back({c[i], x != y});

			if(x != y) q.push_back({c[i-1], 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 = backedgeFrom[i];
			done = 0;

			q.push_back({i, ask(backedges[e][0], 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.push_back(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) {
					int e = a[i];
					uf(U[e], V[e]);
					qry.push_back(e);
				}

				int cnt {};
				for(int e : st) if(uf(U[e], V[e])) {
					qry.push_back(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.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