Submission #840165

#	Time	Username	Problem	Language	Result	Execution time	Memory
840165		KLPP	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	145 ms	852 KiB

longesttrip

#include "longesttrip.h"

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int n;

int p[1000];
vector<int> ord;
bool visited[1000000];
vector<int> tr[1000];
bool table[1000][1000];
vector<int> nvis;
vector<int> T;
int get_vert(int node){
	nvis.clear();
	rep(i,0,n){
		if(!visited[i])nvis.push_back(i);
	}
	if(nvis.empty())return -1;
	if(!are_connected({node},nvis))return -1;
	int lo=0;
	int hi=nvis.size()-1;
	while(hi-lo>0){
		int mid=(hi+lo)/2;
		T.clear();
		rep(i,lo,mid+1)T.push_back(nvis[i]);
		if(are_connected({node},T)){
			hi=mid;
		}else{
			lo=mid+1;
		}
	}
	return nvis[lo];
}
void DFS(int node){
	visited[node]=true;
	ord.push_back(node);
	while(true){
		int a=get_vert(node);
		if(a==-1)break;
		DFS(a);
		tr[node].push_back(a);
		tr[a].push_back(node);
		p[a]=node;
	}
}
bool test(int a, int b){
	if(are_connected({a},{b}))return true;
	return false;
}
std::vector<int> longest_trip(int N, int D)
{
	n=N;
	rep(i,0,n){
		rep(j,0,n)table[i][j]=false;
		p[i]=-1;
		visited[i]=false;
		tr[i].clear();
	}
	vector<int> ans;
	rep(i,0,n){
		if(!visited[i]){
			ord.clear();
			DFS(i);
			int cnt=0;
			int gt=-1;
			rep(j,0,n){
				if((int)tr[j].size()>=3 || (j==i && (int)tr[j].size()>=2)){
					cnt++;
					gt=j;
				}
			}
			pair<int,int> bot={-1,-1};
			rep(j,0,n){
				if(j!=i && (int)tr[j].size()==1){
					if(bot.first==-1)bot.first=j;
					else{
						if(bot.second!=-1)assert(false);
						bot.second=j;
					}
				}
			}
			assert(cnt<=1);
			assert((gt!=-1) || (bot.second==-1));
			if(gt==-1){
				if(ans.size()<ord.size())ans=ord;
			}else{
				ord.clear();
				vector<int> p1;
				vector<int> p2;
				vector<int> p3;
				int x=bot.first;
				int y=bot.second;
				int z=gt;
				while(x!=gt){
					p1.push_back(x);
					x=p[x];
				}
				while(y!=gt){
					p2.push_back(y);
					y=p[y];
				}
				while(p[z]!=-1){
					p3.push_back(p[z]);
					z=p[z];
				}
				reverse(p3.begin(),p3.end());
				trav(a,p3)ord.push_back(a);
				if(p[gt]==-1){
					
					reverse(p2.begin(),p2.end());
					trav(a,p1){
						ord.push_back(a);
					}
					ord.push_back(gt);
					trav(a,p2)ord.push_back(a);
					//~ rep(i,0,(int)ord.size()-1){
						//~ if(!test(ord[i],ord[i+1]))assert(false);
					//~ }
				}else{
					if(test(bot.first,p[gt])){
						reverse(p2.begin(),p2.end());
						trav(a,p1)ord.push_back(a);
						ord.push_back(gt);
						trav(a,p2)ord.push_back(a);
						//~ rep(i,0,(int)ord.size()-1){
							//~ if(!test(ord[i],ord[i+1]))assert(false);
						//~ }
					}else{
						reverse(p1.begin(),p1.end());
						trav(a,p2)ord.push_back(a);
						ord.push_back(gt);
						trav(a,p1)ord.push_back(a);
						//~ rep(i,0,(int)ord.size()-1){
							//~ if(!test(ord[i],ord[i+1]))assert(false);
						//~ }
					}
				}
				if(ans.size()<ord.size())ans=ord;
			}
			rep(j,0,n){
				trav(a,tr[j]){
					if(!test(a,j))assert(false);
				}
				tr[j].clear();
				p[j]=-1;
			}
		}
	}
	
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 19.999999998 / 60