Submission #134704

#	Time	Username	Problem	Language	Result	Execution time	Memory
134704		dvdg6566	Simurgh (IOI17_simurgh)	C++14	70 / 100	589 ms	29692 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define MAXN 510

int N,a,b;
vpi V[MAXN];
vpi edgeList;
vi res,cur;
vpi tmp;
int p[MAXN];
int lowlink[MAXN], depth[MAXN];
int par(int x){return (x==p[x])?x:p[x] = par(p[x]);}
vi bridges;
unordered_map<int,int> M,safe;
	
int gpar,gnode;
vi voided;
vi currentquery;
vi done;

void addsafe(int a, int b){
	safe[a*N+b] = safe[b*N+a] = 1;
}

int find_ind(int a, int b){
	return M[a*N+b];
}
int calls;
int query(int s, int e){
	++calls;
	assert(calls<=12000);
	if (e<s)return 0;
	currentquery.clear();
	int offset = 0;
	for (auto i : voided)if(i!=gpar){
		currentquery.pb(find_ind(gpar, i));
		if (safe[gpar*N+i])++offset;
	}
	for (int i=0;i<SZ(cur);++i){
		// cout<<i<<' '<<cur[i]<<'\n';
		if (i>=s&&i<=e){
			currentquery.pb(find_ind(gnode,cur[i]));
		}else{
			currentquery.pb(find_ind(gpar,cur[i]));
			if (safe[gpar*N+cur[i]])++offset;
		}
	}
	if (gnode != 2)return count_common_roads(currentquery)-offset;
	// for (auto i : currentquery){
	// 	cout<<edgeList[i].f<<' '<<edgeList[i].s<<'\n';
	// }
	return count_common_roads(currentquery)-offset;
}

void dnc(int s, int e, int t){
	if(t==0)return;
	// if (gnode == 2)cout<<"DNC "<<s<<' '<<e<<' '<<t<<'\n';
	if (s == e){
		if (t == 1){
			done.pb(cur[s]);
		}
		return;
	}
	int m = (s+e)/2;
	int l = query(s,m-1);
	int r = query(m+1,e);
	// if (gnode == 2)cout<<m<<' '<<l<<' '<<r<<'\n';
	if (l + r < t){
		done.pb(cur[m]);
	}
	if (s < m)dnc(s,m-1,l);
	if (m < e)dnc(m+1,e,r);
}


void dfs(int x,int p){
	// cout<<"DFS "<<x<<' '<<p<<'\n';
	lowlink[x] = depth[x];
	for (auto v : V[x])if(v.f!=p){
		if (depth[v.f] != -1){
			lowlink[x] = min(lowlink[x], lowlink[v.f]);
			continue;
		}
		depth[v.f] = depth[x]+1;
		dfs(v.f,x);
		lowlink[x] = min(lowlink[x], lowlink[v.f]);
	}
}
 
bool isBridge(int x, int y){
	if (lowlink[x]<=depth[y]&&depth[x]>depth[y])return 0;
	if (lowlink[y]<=depth[x]&&depth[y]>depth[x])return 0;
	// cout<<x<<' '<<y<<'\n';
	return 1;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	N=n;
	for (int i=0;i<SZ(u);++i){
		a=u[i];b=v[i];
		V[a].pb(b,i);V[b].pb(a,i);
		edgeList.pb(a,b);
		M[a*N+b]=i;
		M[b*N+a]=i;
	}
	if (N <= 240){
		a=1;
		memset(depth,-1,sizeof(depth));
		depth[0]=0;
		dfs(0,0);
		for (int i=0;i<SZ(u);++i){
			int a=edgeList[i].f;
			int b=edgeList[i].s;
			if (isBridge(a,b))bridges.pb(i);
		}
 
		// for (auto i : bridges)cout<<i<<'\n';
		if (SZ(bridges) == N-1)return bridges;
 
		for (int i=0;i<N;++i){
			// We want to find all edges with index to a bigger node
			for (int j=0;j<N;++j)p[j]=j;
			cur.clear();
			tmp.clear();
			for (auto it : bridges){
				cur.pb(it);
				p[par(edgeList[it].f)] = par(edgeList[it].s);
			}
			for (int j=0;j<SZ(edgeList);++j){
				pi it = edgeList[j];
				if (it.f == i || it.s == i)continue;
				if (par(it.f) == par(it.s))continue;
				p[par(it.f)] = par(it.s);
				cur.pb(j);
			}
 
			for (auto x : V[i]){
				if (isBridge(i,x.f))continue;
				if (i>x.f)continue;
				cur.pb(x.s);
				// for (auto i : cur)cout<<i<<' ' ;cout<<'\n';
				int t = count_common_roads(cur);
				tmp.pb(x.s,t);
				cur.pop_back();
			}
 
			// cout<<"Current "<<i<<'\n';
			// for (auto x : tmp)cout<<x.f<<' '<<x.s<<'\n';
			int hh = 0;
			// cout<<"V:";for (auto v:res)cout<<v<<' ';cout<<'\n';
			bool gay=1;
 
			for (auto t : res){
				pi it = edgeList[t];
				if (it.f == i || it.s == i){
					cur.pb(t);
					hh = count_common_roads(cur);
					gay=0;
					break;
				}
			}
 
			if (gay){
				int ll = 0;
				for (auto x:tmp)ll = max(ll,x.s);
				for (auto x :tmp)if(x.s==ll)res.pb(x.f);
				continue;
			}
 
			for (auto x : tmp){
				if (x.s == hh)res.pb(x.f);
			}
			
			// for (auto x :tmp)cout<<x.f<<' '<<x.s<<'\n';
			// for (auto x:res)cout<<x<<' ';cout<<'\n';
		}
		for (auto i : bridges)res.pb(i);
		sort(ALL(res));
		res.resize(unique(ALL(res)) - res.begin());
		// assert(SZ(res) == N-1);
		return res;
	}
	// Must be complete graph
	for (int j=0;j<N;++j)p[j]=j;
	for (int i=0;i<SZ(edgeList);++i){
		pi v=edgeList[i];
		if (v.f==0||v.s==0)continue;
		if (par(v.f)==par(v.s))continue;
		p[par(v.f)]=par(v.s);
		cur.pb(i);
	}
	for (auto i :V[0]){
		cur.pb(i.s);
		tmp.pb(i.s,count_common_roads(cur));
		cur.pop_back();
	}
	// for (auto v : tmp)cout<<v.f<<' '<<v.s<<'\n';
	int ll = 0;
	for (auto x:tmp)ll = max(ll,x.s);
	for (auto x :tmp)if(x.s==ll)res.pb(x.f);

	set<int> S;
	queue<pi> q;
	for (int i=1;i<N;++i)S.insert(i);
	voided.pb(0);

	for (auto i : res){
		int x = edgeList[i].f+edgeList[i].s;
		q.push(mp(x,0));
		addsafe(x,0);
		S.erase(x);
		voided.pb(x);
	}

	while(SZ(q)){
		int t = q.front().f;
		int p = q.front().s;
		gpar = p;
		gnode = t;
		// cout<<"Resolve "<<gnode<<' '<<gpar<<'\n';

		q.pop();
		cur.clear();

		for (auto i : S)cur.pb(i);
		// for (auto i :cur)cout<<i<<' ';cout<<'\n';
		// cout<<query(0,SZ(cur))<<'\n';
		dnc(0,SZ(cur),query(0,SZ(cur)));
		// if (gnode == 2)for (auto i : cur)cout<<i <<' ';cout<<'\n';
		for (auto i : done){
			// cout<<"Done "<<i<<'\n';
			res.pb(find_ind(gnode,i));
			// cout<<"Add Edge "<<i<<' '<<gnode<<'\n';
			addsafe(t,i);
			S.erase(i);
			voided.pb(i);
			q.push(mp(i,gnode));
		}
		done.clear();
		// cout<<"Leftover: ";for (auto v : S)cout<<v<<' ';cout<<'\n';
	}
	sort(ALL(res));
	return res;
}

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