제출 #820927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
820927		vjudge1	Simurgh (IOI17_simurgh)	C++17	0 / 100	1 ms	340 KiB

simurgh

#include<bits/stdc++.h>
#include "simurgh.h"

using namespace std;

const int N = 510;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
	vector<int> p;
	vector<vector<int>> st;
	void init(int n) {
		p.resize(n), st.resize(n);
		for(int i = 0; i < n; i++) {
			p[i] = i;
			st[i].push_back(i);
		}
	}
	int find(int x) {
		return p[x] = (p[x] == x ? x : find(p[x]));
	}
	void merge(int u, int v) {
		u = find(u);
		v = find(v);
		if(u == v) return;
		if((int)st[u].size() < (int)st[v].size()) 
			swap(u, v);
		p[v] = u;
		for(auto c : st[v]) 
			st[u].push_back(c);
	}
};

struct edge {
	int u, v, inx;
	int to(int u) {
		return (this->u == u ? this->v : this->u);
	}
};

DSU ds;
vector<int> g[N];
edge e[N * N];
int type[N * N], royal_cnt = 0;
// 0 = unknown, 1 = royal, 2 = common
void coloring(int x, int cl) {
	x = ds.find(x);
	for(int c : ds.st[x]) {
		type[c] = cl;
		royal_cnt += (cl == 1);
	}
}

int n, m;
int tin[N], tout[N], T = 0;
vector<bool> vis;
vector<int> used;

void dfs(int s = 0) {
	vis[s] = 1;
	tin[s] = T++;
	for(int i : g[s]) {
		if(!vis[e[i].to(s)] && !type[i]) {
			used.push_back(i);
			dfs(e[i].to(s));
		}
	}
	for(int i : g[s]) {
		if(!vis[e[i].to(s)] && type[i] == 1) {
			used.push_back(i);
			dfs(e[i].to(s));
		} 
	}
	tout[s] = T++;
}

bool up(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}
vector<int> travel() {
	vis.assign(n, false);
	used.clear();
	T = 0;
	dfs();
	return used;
}

bool isAble(int i, int j) {
	int u = e[i].u, v = e[i].v;
	int x = e[i].u, y = e[i].v;
	if(tin[u] > tin[v]) swap(u, v);
	if(tin[x] > tin[y]) swap(x, y);
	return (up(v, y) && up(x, u));
}

vector<int> find_roads(int N, vector<int> u, vector<int> v) {
	n = N;
	m = (int)u.size();
	for(int i = 0; i < m; i++) {
		e[i] = {u[i], v[i], i}; 
		g[u[i]].push_back(i);
		g[v[i]].push_back(i);
	}
	ds.init(m);
	while(royal_cnt < n - 1) {
		vector<int> w = travel();
		int res0 = count_common_roads(w);
		if(res0 == n - 1) return w;
		vector<int> un_w;
		for(int inx : w) {
			if(!type[inx])
				un_w.push_back(inx);
		}
		int chosen = un_w[rnd() % ((int)un_w.size())], sec_ch = -1;
		vector<int> rep_e;
		for(int i = 0; i < m; ++i) {
			if(isAble(chosen, i)) 
				rep_e.push_back(i);
		}
		if(rep_e.empty()) {
			coloring(chosen, 1);
			continue;
		}
		for(int c : rep_e) {
			if(type[c]) {
				sec_ch = c;
				break;
			}
		}

		if(sec_ch != -1) {
			w.erase(find(w.begin(), w.end(), chosen));
			w.push_back(sec_ch);
			int res1 = count_common_roads(w);
			if(res0 == res1) coloring(chosen, type[sec_ch]);
			else coloring(chosen, 1 + (res0 < res1));
		} else {
			sec_ch = rep_e[rnd() % (int)rep_e.size()];
			w.erase(find(w.begin(), w.end(), chosen));
			w.push_back(sec_ch);
			int res1 = count_common_roads(w);
			if(res0 == res1) ds.merge(chosen, sec_ch);
			else {
				if(res0 < res1) 
					coloring(chosen, 2),
					coloring(sec_ch, 1);
				else 
					coloring(chosen, 1),
					coloring(sec_ch, 2);
			}
		}
	}
	vector<int> r;
	for(int i = 0; i < m; i++) {
		if(type[i] == 1) 
			r.push_back(i);
	}
	return r;
}

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