Submission #73731

#	Time	Username	Problem	Language	Result	Execution time	Memory
73731		hamzqq9	Simurgh (IOI17_simurgh)	C++14	51 / 100	264 ms	5488 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
#define ii pair<int,int>
#define st first
#define nd second
#define pb push_back
#define iii pair<ii,int>
#define all(x) x.begin(),x.end()
#define ppb pop_back
#define ll long long
#define sz(x) ((int)x.size())
using namespace std;

int n,m,inus,ous;
int normal;
vector<int> inmst,path,ans;
int pos[505*505];
int ata[505],ok[505*505];
vector<iii> rem,e;
vector<ii> v[505];
int flag,reach;

int bul(int x) {

	if(ata[x]==x) return x;

	return ata[x]=bul(ata[x]);

}

void finish(int w) {

	/*for(int i=0;i<sz(path);i++) cerr<<path[i]<<' ';

	cerr<<"\n-------------------\n";*/

	int bef=0;

	vector<int> ress;

	for(int i=0;i<sz(path);i++) {

		if(bef && ok[path[i]]!=0) {

			continue ;

		}

		bef=max(bef,ok[path[i]]);

		swap(inmst[pos[path[i]]],w);

		int cur=count_common_roads(inmst);

		swap(inmst[pos[path[i]]],w);

		/*if(w==2 && path[i]==6) {

			//cerr<<"spe   "<<normal<<' '<<cur<<'\n'<<pos[6]<<'\n';
/
			/(int j=0;j<sz(inmst);j++) cerr<<inmst[j]<<" ";

			cerr<<endl;

		}*/

		ress.pb(cur);

		if(cur>normal || (ok[path[i]]==1 && cur==normal)) {

			flag=1;

		}


		if(cur<normal || (ok[path[i]]==2 && cur==normal)) {

			flag=-1;

		}

	}

	int pr=0;
	int okk=0;

	if(flag==1) {

		for(int i=0;i<sz(path);i++) {

			if(ok[path[i]] && okk) continue ;

			okk+=ok[path[i]];

			if(ress[pr]==normal && !ok[path[i]]) {

				ok[path[i]]=1;

				ans.pb(path[i]);

			}
			else if(!ok[path[i]]) {

				ok[path[i]]=2;

			}

			++pr;

		}

	}
	else if(flag==-1) {

		for(int i=0;i<sz(path);i++) {

			if(ok[path[i]] && okk) continue ;

			okk+=ok[path[i]];

			if(ress[pr]==normal && !ok[path[i]]) {

				ok[path[i]]=2;

			}
			else if(!ok[path[i]]) {

				ok[path[i]]=1;
				ans.pb(path[i]);

			}

			++pr;

		}

		flag=0;

	}  
	else {

		for(int i=0;i<sz(path);i++) {

			ok[path[i]]=2;

		}

	}

}

void dfs(int node,int ata,int to,int w) {

	if(reach) return ;

	if(node==to) {

		finish(w);

		reach=1;

		return ;

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		path.pb(i.nd);

		dfs(i.st,node,to,w);

		path.ppb();

	}

}

void make_mst() {

	for(int i=0;i<n;i++) ata[i]=i;

	for(auto i:e) {

		if(bul(i.st.st)!=bul(i.st.nd)) {

			inmst.pb(i.nd);

			pos[i.nd]=sz(inmst)-1;

			//cerr<<i.nd<<' '<<pos[i.nd]<<endl;

			ata[bul(i.st.st)]=bul(i.st.nd);

			v[i.st.st].pb({i.st.nd,i.nd});
			v[i.st.nd].pb({i.st.st,i.nd});

		}
		else {

			rem.pb(i);

		}

	}

	normal=count_common_roads(inmst);

}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	
	m=sz(u);
	::n=n;

	for(int i=0;i<m;i++) {

		e.pb({{u[i],v[i]},i});

	}

	random_shuffle(all(e));

	make_mst();

	//cerr<<normal<<endl;

	//cerr<<"----------------\n";

	//for(int i=0;i<sz(inmst);i++) cerr<<inmst[i]<<' ';

	//cerr<<"---------------\n";

	for(auto edge:rem) {

		flag=0;
		reach=0;

		//cerr<<edge.nd<<endl;

		dfs(edge.st.st,-1,edge.st.nd,edge.nd);

		if(flag) {

			//cerr<<"OK-->"<<edge.nd<<endl;

			ans.pb(edge.nd);

		}

		if(sz(ans)==n-1) break ;

	}

	//cerr<<"-----------------\n";

	for(int i=0;i<sz(inmst);i++) if(sz(ans)!=n-1 && !ok[inmst[i]]) ans.pb(inmst[i]);

	return ans;

}

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