Submission #302337

#	Time	Username	Problem	Language	Result	Execution time	Memory
302337		TMJN	Simurgh (IOI17_simurgh)	C++17	19 / 100	229 ms	4600 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,D[500],ID[500][500];
bool B[500][500];

vector<int>find_roads(int n,vector<int>u,vector<int>v){
	N=n;
	M=u.size();
	assert(M==N*(N-1)/2);
	for(int i=0;i<N;i++){
		D[i]=0;
		for(int j=0;j<N;j++){
			ID[i][j]=B[i][j]=0;
		}
	}
	for(int i=0;i<M;i++){
		ID[u[i]][v[i]]=ID[v[i]][u[i]]=i;
	}
	for(int i=0;i<N;i++){
		vector<int>v;
		for(int j=0;j<N;j++){
			if(i==j)continue;
			v.push_back(ID[i][j]);
		}
		D[i]=count_common_roads(v);
	}
	int uni,K;
	uni=-1;
	K=-1;
	for(int i=0;i<N;i++){
		if(D[i]==1){
			uni=i;
			break;
		}
	}
	for(int i=uni+1;i<N;i++){
		if(D[i]==1){
			vector<int>v;
			for(int j=0;j<N;j++){
				if(j==uni||j==i)continue;
				v.push_back(ID[i][j]);
			}
			v.push_back(-1);
			for(int j=0;j<N;j++){
				if(j==uni)continue;
				if(j==i)continue;
				v.back()=ID[uni][j];
				if(count_common_roads(v)==2){
					K=j;
					break;
				}
			}
			break;
		}
	}
	B[uni][K]=B[K][uni]=true;
	for(int i=0;i<N;i++){
		if(i==uni)continue;
		int last_val=-1;
		for(int j=0;j<D[i]-(i==K);j++){
			int l,r;
			l=last_val;
			r=N-1;
			while(l+1!=r){
				int m=(l+r)/2;
				vector<int>v;
				int c=0;
				v.push_back(ID[uni][i]);
				if(i==K)c=1;
				for(int k=0;k<=last_val;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=m+1;k<N;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=last_val+1;k<=m;k++){
					if(k==uni||k==i)continue;
					v.push_back(ID[i][k]);
				}
				if(count_common_roads(v)>c){
					r=m;
				}
				else{
					l=m;
				}
			}
			B[i][r]=B[r][i]=true;
			last_val=r;
		}
	}
	vector<int>res;
	for(int i=0;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(B[i][j]){
				res.push_back(ID[i][j]);
			}
		}
	}
	return res;
}

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