Submission #1076193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076193		Abito	Simurgh (IOI17_simurgh)	C++17	30 / 100	2015 ms	64304 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define pb push_back
#define ask count_common_roads
using namespace std;
const int N=4e4+5;
int par[N],sz[N];
bool in[N],know[N];
map<vector<int>,int> mp;
int getpar(int x){
	if (x==par[x]) return x;
	return par[x]=getpar(par[x]);
}
bool link(int x,int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return 0;
	if (sz[x]>sz[y]) swap(x,y);
	sz[y]+=sz[x];
	par[x]=y;
	return 1;
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m=u.size();
	for (int i=0;i<m;i++) u[i]++,v[i]++;
	for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
	vector<int> r;
	for (int i=0;i<m;i++){
		if (link(u[i],v[i])) r.pb(i),in[i]=1;
	}
	int ans=mp[r]=ask(r),q=1;
	for (int i=0;i<m && ans<n-1;i++){
		if (!in[i] || know[i]) continue;
		int s=i;
		for (int j=0;j<m;j++){
			if (in[j] || know[j]) continue;
			vector<int> t;
			for (auto x:r) if (x!=i) t.pb(x);
			t.pb(j);
			for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
			int tree=0;
			for (auto x:t) tree+=link(u[x],v[x]);
			if (tree!=n-1) continue;
			sort(t.begin(),t.end());
			int h;
			if (mp.find(t)==mp.end()){
				assert(q<30000);
				q++;
				mp[t]=ask(t);
			}
			h=mp[t];
			if (h<=ans) continue;
			s=j;
			in[s]=1;
			in[i]=0;
			swap(r,t);
			ans=h;
			break;
		}
		know[i]=1;
		know[s]=1;
	}	
	return r;
}

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