Submission #1055786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055786		ReLice	Simurgh (IOI17_simurgh)	C++17	100 / 100	120 ms	9040 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define ll int
#define ins insert
#define pb push_back
#define pf push_front
#define pob pop_badk()
#define pof pop_front()
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;

template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}

const ll N = 5e2 + 7;
const ll M = N * N;

vector<pll> g(N);
vll u, v;
ll n, m;
ll p[N], d[N];
ll vis[M];
ll royal[M];
ll ct;
pair<ll,ll> mx[N];

ll pr(ll a, ll ed){
	if(a == v[ed]) return u[ed];
	if(a == u[ed]) return v[ed];
	return -1;
}

int qry(vector <int> x){
	// check
	vll p(n), siz(n);
	for(int i=0;i<n;i++){p[i]=i,siz[i]=1;}
	
	function<int(int)> anc = [&] (ll a){
		return (a==p[a] ? a : p[a] = anc(p[a]));
	};
	
	auto uni = [&] (ll a, ll b){
		a = anc(a);
		b = anc(b);
		
		if(a == b) return false;
		if(siz[a] > siz[b]) swap(a,b);
		
		siz[b] += siz[a];
		p[b] = a;
		return true;
	};
	
	for(auto i : x){
		assert(uni(u[i], v[i]));
	}
	return count_common_roads(x);
}

ll pr(ll a){return pr(a, p[a]); }

void build_tree(ll v){
	mx[v] = {d[v], -1};
	//~ cout<<v<<endl;
	for(auto [to, r] : g[v]){
		if(r == p[v])continue;
		if(d[to] != d[n]) {
			mx[v] = min(mx[v], {d[to], r});
			continue;
		}
		
		
		d[to] = d[v] + 1;
		p[to] = r;
		
		build_tree(to);
		
		mx[v] = min(mx[v], mx[to]);
	}
}

ll check(ll v, ll top){
	while(pr(v) != top){
		v = pr(v);
	}
	if(vis[p[v]]) return 2;
	return 1;
}

vll get_path(ll v, ll top){
	vll path;
	while(v != top){
		path.pb(v);
		v = pr(v);
	}
	reverse(all(path));
	return path;
}

vll get_init(){
	vll v(n - 1);
	for(ll i=1;i<n;i++){
		v[i - 1] = p[i];
	}
	return v;
}

void tp1(ll u, ll ed){// if don't know any edges
	ll i;
	ll top = pr(u, ed);
	
	vll v = get_init();
	vll path = get_path(u, top);
	
	vll res;
	ll mn = ct, mx = ct;
	for(auto i : path){
		v[i - 1] = ed;
		
		ll x = qry(v);
		res.pb(x);
		mx = max(mx, x);
		mn = min(mn, x);
		
		v[i - 1] = p[i];
	}
	
	for(i=0;i<(ll)res.size();i++){
		ll a = path[i];
		
		vis[p[a]] = 1;

		if(res[i] == mx){
			royal[p[a]] = 0;
		}
		else royal[p[a]] = 1;
	}
	
	vis[ed] = 1;
	if (ct == mx){
		royal[ed] = 0;
	}else royal[ed] = 1;
}

void tp2(ll u, ll ed){// if we know some edges
	if(vis[p[u]]) return;
	
	ll top = pr(u, ed);
	
	vll v = get_init();
	vll path = get_path(u, top);
	
	top = path[0];
	
	v[top - 1] = ed;
	ll x = qry(v);
	v[top - 1] = p[top];
	
	vis[ed] = 1;
	royal[ed] = x - ( ct - royal[p[top]] );
	
	for(auto i : path){
		if(vis[p[i]]) continue;
		vis[p[i]] = 1;
		
		v[i - 1] = ed;
		ll x = qry(v);
		v[i - 1] = p[i];
		
		// x = ct - royal[i] + royal[ed]
		// royal[i] = ct - x + royal[ed] 
		vis[p[i]] = 1;
		royal[p[i]] = ct - x + royal[ed];
	}
}

void calc(ll v){
	if(mx[v].sc == -1){
		if(p[v] >= 0){
			vis[p[v]] = 1;
			royal[p[v]] = 1;
		}
	} 
	else {
		ll top = pr(v, mx[v].sc);
		if(top >= 0 && d[top] < d[v]){
			//~ cout<<v<<' '<<top<<endl;
			if(check(v, top) == 1) tp1(v, mx[v].sc);
			else tp2(v, mx[v].sc);
		}
	}
	
	
	for(auto [to, r] : g[v]){
		if(pr(to) != v) continue;
		
		calc(to);
	}
}

void calc_tree(){
	memset(d, 0x3f, sizeof(d));
	p[0] = -1;
	d[0] = 0;
	build_tree(0);
	
	ct = qry(get_init());
	
	calc(0);
}

ll count(deque<ll> &ed, vll &v, ll m, ll u){
	ll cur = ct;
	for(ll i=0;i<m;i++){
		ll a = pr(u, ed[i]);
		
		cur -= royal[p[a]];
		
		v[a - 1] = ed[i];
	}
	ll x = qry(v);
	for(ll i=0;i<m;i++){
		ll a = pr(u, ed[i]);
		
		v[a - 1] = p[a];
	}
	return x - cur;
}

void find_others(ll u){
	vll v = get_init();
	deque<ll> ed;
	
	for(auto [to, r] : g[u]){
		if(vis[r]) continue;
		vis[r] = 1;
		ed.pb(r);
	}
	
	ll x = count(ed, v, (ll)ed.size(), u);
	
	//~ cout<<u<<'*'<<x<<endl;
	//~ for(auto i : ed) cout<<u<<' '<<pr(u, i)<<endl;
	//~ cout<<endl;
	for(ll i=1;i<=x;i++){
		ll l = 0, r = (ll)ed.size();
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(count(ed, v, m, u) == 0) l = m;
			else r = m;
		}
		
		royal[ed[r-1]] = 1;
		while(r--) ed.pof;
	}
	
	for(auto [to, r] : g[u]){
		if(pr(to) != u) continue;
		
		find_others(to);
	}
}

vector<int> find_roads(int N, vector<int> U, vector<int> V) {
	ll i;
	m = U.sz;
	n = N, u = U, v = V;
	
	for(i=0;i<m;i++){
		g[u[i]].pb({v[i],i});
		g[v[i]].pb({u[i],i});
	}
	
	calc_tree();
	
	//~ cout<<endl;
	//~ for(ll i=0;i<m;i++)if(vis[i])cout<<i<<' '<<royal[i]<<endl;
	
	find_others(0);
	
	//~ for(i=1;i<n;i++)cout<<u[p[i]]<<' '<<v[p[i]]<<endl;
	
	vll v;
	
	for(i=0;i<m;i++){
		//~ if(vis[i])cout<<i<<' '<<royal[i]<<endl;
		if(royal[i])v.pb(i);
	}
	
	return v;
}

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