Submission #135056

#	Time	Username	Problem	Language	Result	Execution time	Memory
135056		nvmdava	Simurgh (IOI17_simurgh)	C++17	100 / 100	787 ms	4972 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>
#define M 505

vector<pair<int, int> > e;
bool ans[M * M], ch[M * M], in[M];
vi inq, tr, adj[M], vall, qq, ret, cyc, fin, onn, off, nu;
int p[M], t, pp[M], d[M], n, m;

int get(int v, int i){
	return e[i].ff + e[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 dsu(int v, int u){
	p[v = find(v)] = u = find(u);
	return v != u;
}

int ask(){
	reset();
	for(int x : inq)
		dsu(e[x].ff, e[x].ss);
	t = 0;
	for(int x : tr)
		if(dsu(e[x].ff, e[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(d[u]) continue;
		pp[u] = x;
		d[u] = d[v] + 1;
		tr.pb(x);
		dfs(u);
	}
}

int fexc(int a){
   inq.clear();
   for(int x : cyc)
      if(x != a)
         inq.pb(x);
	return ask();
}

void cycle(){
	if(fin.empty()) return;
   int lo;
	if(onn.empty() && off.empty()){
		lo = -1;
		vall = nu;
		for(int x : cyc)
			vall.pb(fexc(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 {
      lo = off.empty() ? fexc(onn[0]) : fexc(off[0]) - 1;
		for(int x : fin){
			ch[x] = 1;
			ans[x] = fexc(x) == lo;
		}
	}
}

void tree(){
	for(int i = 0; i < m; i++){
      int v = e[i].ff, u = e[i].ss;
		if(d[v] < d[u]) swap(v, u);
		if(d[v] - d[u] == 1) continue;
		cyc = fin = off = onn = nu;
		cyc.pb(i);
		int s = v;
		while(s != u){
			cyc.pb(pp[s]);
			if(ch[pp[s]] == 0) fin.pb(pp[s]);
			else if(ans[pp[s]] == 1) onn.pb(pp[s]);
			else off.pb(pp[s]);
			s = get(s, pp[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) / 2;
		inq = nu;
		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);
		e.pb({v[i], u[i]});
	}
	d[0] = 1;
	dfs(0);
	tree();
	do{
		memset(in, 0, sizeof in);
		qq = nu;
		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