Submission #778265

#	Time	Username	Problem	Language	Result	Execution time	Memory
778265		CSQ31	Simurgh (IOI17_simurgh)	C++17	51 / 100	272 ms	23940 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN = 2e5;
int par[MAXN],szz[MAXN],good[MAXN],tree[MAXN];
vector<pii>adj[MAXN],ed;
int find(int x){
	if(x==par[x])return x;
	return par[x] = find(par[x]);
}
bool unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	if(szz[a] > szz[b])swap(a,b);
	par[a] = b;
	szz[b]+=szz[a];
	return 1;
}
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i;
		szz[i] = 1;
	}
}
set<int>edges;
vector<int>edge;
int nn;
int Q = 0;
int ask(){
	Q++;
	assert(Q<=8500);
	vector<int>r;
	if(edges.empty())for(int x:edge)r.pb(x);
	else for(int x:edges)r.pb(x);
	//assert(sz(r)==nn-1);
	return count_common_roads(r);
}

pii p[MAXN];
int dep[MAXN],vis[MAXN],glob;
void dfs(int v,int u){
	vis[v] = 1;
	for(pii z:adj[v]){
		int x = z.fi;
		int id = z.se;
		if(vis[x] || x==u)continue;
		tree[id] = 1;
		edges.insert(id);
		dep[x] = dep[v]+1;
		p[x] = {v,id};
		dfs(x,v);
	}
}
void dfs2(int v,int u){
	
	for(pii z:adj[v]){
		int x = z.fi;
		int id = z.se;
		if(tree[id]){
			if(x!=u)dfs2(x,v);
			continue;
		}
		if(dep[x] > dep[v])continue; //go downwards
		
		vector<int>path,res;
		int cur = v;
		while(cur != x){
			path.pb(p[cur].se);
			cur = p[cur].fi;
		}
		//for(int e:path)cout<<e<<" ";
		//cout<<'\n';
		int have = 0;
		for(int e:path)have += (good[e] == -1);
		if(!have)continue; //if all tree edge part of this cycle is known,skip
		edges.insert(id);
		if(have == sz(path)){ //everything is unknown
			//cout<<"case 1"<<'\n';
			for(int e:path){
				edges.erase(e);
				res.pb(ask());
				edges.insert(e);
			}
			path.pb(id);
			res.pb(glob);
			int s = sz(path);
			for(int i=0;i<s;i++){
				int j = (i+s-1) % s;
				if(res[i] == res[j])continue;
				good[path[i]] = 1;
				good[path[j]] = 0;
				if(res[i] > res[j])swap(good[path[i]],good[path[j]]);
			}
			for(int i=0;i<s;i++){
				int j = (i+s-1) % s;
				if(good[path[j]] >= 0 && res[i] == res[j])good[path[i]] = good[path[j]];
			}
			for(int i=s-1;i>=0;i--){
				int j = (i+1) % s;
				if(good[path[j]] >= 0 && res[i] == res[j])good[path[i]] = good[path[j]];
			}
			for(int x:path){
				if(good[x] == -1)good[x] = 0;
			}
		}else{
			//cout<<"case 2"<<'\n';
			if(good[id] == -1){
				for(int e:path){
					if(good[e] == -1)continue;
					edges.erase(e);
					int res2 = ask();
					edges.insert(e);
					if(res2 == glob)good[id] = good[e];
					else if(res2 > glob)good[id] = 1; 
					else good[id] = 0;
					break;
				}
			}
			//cout<<good[id]<<'\n';
			for(int e:path){
				if(good[e] != -1)continue;
				edges.erase(e);
				int res2 = ask();
				edges.insert(e);
				if(res2 == glob)good[e] = good[id];
				else if(res2 > glob)good[e] = 0;
				else good[e] = 1;
			}
		}
		edges.erase(id);
	}
}
vector<int>e,solved;
void solve(int l,int r){
	if(l>r)return;
	init(nn);
	edge.clear();
	for(int i=l;i<=r;i++){
		if(unite(ed[e[i]].fi,ed[e[i]].se))edge.pb(e[i]);
	}
	int tot = 0;
	
	for(int i:solved){
		if(unite(ed[i].fi,ed[i].se)){
			edge.pb(i);
			tot+=good[i];
		}
		if(sz(edge)==nn-1)break;
		
	}
	int res = ask();
	edge.clear();
	if(res == tot){
		for(int i=l;i<=r;i++)good[e[i]] = 0;
		return;
	}else if(res == tot + r-l+1){
		for(int i=l;i<=r;i++)good[e[i]] = 1;
		return;
	}
	
	int mid = (l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	
	
}
mt19937 seed(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> find_roads(int N,vector<int> u,vector<int> v) {
	nn = N;
	int n = N;
	int m = sz(u);
	for(int i=0;i<m;i++)ed.pb({v[i],u[i]});
	for(int i=0;i<m;i++){
		good[i] = -1;
		adj[u[i]].pb({v[i],i});
		adj[v[i]].pb({u[i],i});
	}
	dfs(0,-1);
	glob = ask();
	dfs2(0,-1);
	assert(Q<=1000);

	for(int x:edges){
		if(good[x]==-1)good[x] = 1; //this is a bridge	
	}
	for(int i=0;i<m;i++){
		if(good[i]>=0)solved.pb(i);
	}
	edges.clear();
	for(int i=0;i<n;i++){
		e.clear();
		for(pii x:adj[i]){
			if(good[x.se] == -1 && x.fi < i)e.pb(x.se);
		}
		if(e.empty())continue;
		solve(0,sz(e)-1);
		for(int x:e)solved.pb(x);
	}
	vector<int>ans;
	for(int i=0;i<m;i++){
		if(good[i] == 1)ans.pb(i);
	}
	return ans;
}

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