제출 #399799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399799		kshitij_sodani	Simurgh (IOI17_simurgh)	C++14	30 / 100	238 ms	3160 KiB

simurgh

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
#define ask count_common_roads
#include "simurgh.h"
int par[501];
vector<pair<int,int>> adj[501];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int ca=-1;
vector<int> pp;
vector<int> pp2;
void dfs(int no,int par2=-1){
	if(no==ca){
		pp2=pp;
	}
	for(auto j:adj[no]){
		if(j.a!=par2){
			pp.pb(j.b);
			dfs(j.a,no);
			pp.pop_back();
		}
	}
}
vector<int> find_roads(int n,vector<int> uu,vector<int> vv) {
	int m=uu.size();
	for(int i=0;i<n;i++){
		par[i]=i;
	}
	vector<pair<pair<int,int>,int>> cur;
	vector<pair<pair<int,int>,int>> cur2;
	for(int i=0;i<m;i++){
		int x=find(uu[i]);
		int y=find(vv[i]);
		if(x!=y){
			par[x]=y;
			cur.pb({{uu[i],vv[i]},i});
		}
		else{
			cur2.pb({{uu[i],vv[i]},i});
		}
	}
	mt19937 rng;
	rng=mt19937(chrono::steady_clock::now().time_since_epoch().count());
	int val;
	vector<int> ee;
	for(auto j:cur){
		ee.pb(j.b);
	}
	val=ask(ee);
	/*for(auto j:ee){
		cout<<j<<",";
	}
	cout<<endl;*/
	shuffle(cur2.begin(),cur2.end(),rng);
	for(auto j:cur2){
		if(val==n-1){
			break;
		}
		for(int i=0;i<n;i++){
			adj[i].clear();
		}
		for(auto i:cur){
			adj[i.a.a].pb({i.a.b,i.b});
			adj[i.a.b].pb({i.a.a,i.b});
		}
		ca=j.a.b;
		dfs(j.a.a);
		shuffle(pp2.begin(),pp2.end(),rng);
		for(auto i:pp2){
			/*if(j.b==4){
				cout<<i<<"<<"<<endl;
			}*/
			vector<int> ff;
			for(auto jj:ee){
				if(jj!=i){
					ff.pb(jj);
				}
			}
			ff.pb(j.b);
			int val2=ask(ff);
			/*
			if(j.b==4){
				for(auto j:ff){
					cout<<j<<".";
				}
			
				cout<<endl;
				cout<<val<<"::"<<endl;
				cout<<val2<<"::"<<endl;
			}*/
			if(val2<val){
				break;
			}
			if(val2==val){
				continue;
			}
			vector<pair<pair<int,int>,int>> cur3;
			for(auto ii:cur){
				if(ii.b==i){
					continue;
				}
				cur3.pb(ii);
			}
			cur3.pb(j);
			cur=cur3;
			val=val2;
			ee=ff;
			/*for(auto j:ff){
				cout<<j<<",";
			}
			cout<<endl;*/

			break;
		}


	}
	return ee;
}

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