Submission #1201710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201710		8pete8	Simurgh (IOI17_simurgh)	C++20	51 / 100	92 ms	2632 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int mxn=505;

int pa[mxn+10];
vector<int>have[mxn+10];
int find(int u){return (pa[u]==u)?u:pa[u]=find(pa[u]);}
bool merge(int a,int b){
	a=find(a),b=find(b);
	if(a==b)return false;
	if(have[a].size()<have[b].size())swap(a,b);
	pa[b]=a;
	for(auto i:have[b])have[a].pb(i);
	return true;
}
void init(int n){
	for(int i=0;i<=n;i++){
		pa[i]=i;
		have[i].clear();
		have[i].pb(i);
	}
}

int mark[mxn+10];
int E[mxn+10][mxn+10],done[mxn+10][mxn+10];
int bro=0;
vector<int> find_roads(int n, vector<int> u,vector<int> v) {
	vector<int>ans;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)E[i][j]=-1;
	for(int i=0;i<u.size();i++){
		E[u[i]][v[i]]=i;
		E[v[i]][u[i]]=i;
	}
	for(int node=0;node<n;node++){
		init(n);
		vector<int>edge;
		for(int j=0;j<u.size();j++)if(u[j]!=node&&v[j]!=node&&merge(u[j],v[j])){
			edge.pb(j);
		}
		vector<int>head;
		vector<int>addedge;
		for(int i=0;i<n;i++)if(i!=node&&!mark[find(i)]){
			head.pb(find(i));
			for(auto j:have[find(i)])if(E[node][j]!=-1){
				addedge.pb(E[node][j]);
				break;
			}
			if(addedge.size()!=head.size())assert(0);
			mark[find(i)]=1;
		}
		for(int i=0;i<n;i++)mark[i]=0;
		for(int i=0;i<head.size();i++){
			for(int j=0;j<addedge.size();j++)if(j!=i)edge.pb(addedge[j]);
			int c=0,mx=0;
			vector<int>val;
			for(auto j:have[head[i]]){
				if(E[node][j]==-1){
					val.pb(-1);
					continue;
				}
				if(j<node){
					if(c>0||done[node][j]==0){
						val.pb(-1);
						continue;
					}
					c++;
				}
				edge.pb(E[node][j]);

				bro++;
				if(bro>30000)assert(0);

				val.pb(count_common_roads(edge));
				mx=max(mx,val.back());
				edge.pop_back();
			}
			if(mx==0)assert(0);
			for(int j=0;j<have[head[i]].size();j++)if(val[j]==mx&&have[head[i]][j]>node){
				done[node][have[head[i]][j]]=1;
				done[have[head[i]][j]][node]=1;
				ans.pb(E[node][have[head[i]][j]]);
			}
			for(int j=0;j<addedge.size()-1;j++)edge.pop_back();
		}
	}
	return ans;
}

/*
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5


5 9
2 1
1 4
4 0
0 3
3 4
2 4
1 3
0 2
0 1
0 1 2 3 
*/

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