제출 #135022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135022		nvmdava	Simurgh (IOI17_simurgh)	C++17	100 / 100	740 ms	4980 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>

vector<pair<int, int> > edge;
bool ans[150000], ch[150000], in[505];
vi inq, tr, adj[505], vall, qq, ret, cyc, fin, onn, off;

int p[505], t, par[505], dep[505], n, m;

int get(int v, int i){
	return edge[i].ff + edge[i].ss - v;
}

void reset(){
	for(int i = 0; i < n; i++)
		p[i] = i;
}

int find(int v){
	return v == p[v] ? v : p[v] = find(p[v]);
}

bool merge(int v, int u){
	v = find(v);
	u = find(u);
	if(v == u) return 0;
	p[v] = u;
	return 1;
}

int ask(){
	reset();
	for(int x : inq)
		merge(edge[x].ff, edge[x].ss);
	t = 0;
	for(int x : tr){
		if(merge(edge[x].ff, edge[x].ss)){
			inq.pb(x);
			t += ans[x];
		}
	}
	return count_common_roads(inq);
}

void dfs(int v){
	for(int x : adj[v]){
		int u = get(v, x);
		if(dep[u]) continue;
		par[u] = x;
		dep[u] = dep[v] + 1;
		tr.pb(x);
		dfs(u);
	}
}

int fillexc(int x){
	inq = cyc;
	for(int& a : inq){
		if(a == x){
			swap(a, inq.back());
			inq.pop_back();
			break;
		}
	}
	return ask();
}

void cycle(){
	if(fin.empty()) return;
   int lo;
	if(onn.empty() && off.empty()){
		lo = -1;
		vall.clear();
		for(int& x : cyc)
			vall.pb(fillexc(x));
		for(int& x : vall)
			lo = max(lo, x);
		for(int i = cyc.size() - 1; i >= 0; i--){
			ch[cyc[i]] = 1;
			ans[cyc[i]] = (lo - vall[i]);
		}
	} else {
		if(off.empty())
			lo = fillexc(onn[0]);
		else
			lo = fillexc(off[0]) - 1;
		for(int x : fin){
			ch[x] = 1;
			ans[x] = (fillexc(x) == lo);
		}
	}
}

void tree(){
	for(int i = 0; i < m; i++){
		if(dep[edge[i].ff] < dep[edge[i].ss]) swap(edge[i].ff, edge[i].ss);
		if(dep[edge[i].ff] - dep[edge[i].ss] == 1) continue;
		cyc.clear(); fin.clear(); off.clear(); onn.clear();
		cyc.pb(i);
		int s = edge[i].ff;
		while(s != edge[i].ss){
			cyc.pb(par[s]);
			if(ch[par[s]] == 0) fin.pb(par[s]);
			else if(ans[par[s]] == 1) onn.pb(par[s]);
			else off.pb(par[s]);
			s = get(s, par[s]);
		}
		cycle();
	}
	for(int x : tr)
		if(!ch[x])
			ch[x] = ans[x] = 1;
}

void dfs2(int v){
	in[v] = 1;
	for(int i = adj[v].size() - 1; i >= 0; i--){
		if(ch[adj[v][i]]){
			swap(adj[v][i], adj[v].back());
			adj[v].pop_back();
			continue;
		}
		int u = get(v, adj[v][i]);
		if(in[u]) continue;
		qq.pb(adj[v][i]);
		dfs2(u);
	}
}

void vsolve(){
	if(qq.empty()) return;
	inq = qq;
	if(ask() == t){
		for(int& x : qq){
			ch[x] = 1;
			ans[x] = 0;
		}
		return;
	}
	int l = 0, r = qq.size() - 1;
	while(l != r){
		int m = (l + r) >> 1;
		inq.clear();
		for(int i = 0; i <= m; i++)
			inq.pb(qq[i]);
		if(ask() == t)
         l = m + 1;
		else
         r = m;
	}
	for(int i = 0; i < r; i++){
		ch[qq[i]] = 1;
		ans[qq[i]] = 0;
	}
	ch[qq[r]] = ans[qq[r]] = 1;
}


vi find_roads(int N, vi u, vi v) {
	n = N;
	m = u.size();
	for(int i = 0; i < m; i++){
		adj[v[i]].pb(i);
		adj[u[i]].pb(i);
		edge.pb({v[i], u[i]});
	}
	dep[0] = 1;
	dfs(0);
	tree();
	do{
		memset(in, 0, sizeof in);
		qq.clear();
		for(int i = 0; i < n; i++)
			if(!in[i])
            dfs2(i);
		vsolve();
	} while(!qq.empty());
	for(int i = 0; i < m; i++)
		if(ans[i])
         ret.pb(i);
	return ret;
}

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