Submission #956149

#	Time	Username	Problem	Language	Result	Execution time	Memory
956149		MilosMilutinovic	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	801 ms	1236 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
 
#define pb push_back
 
using namespace std;
 
bool con[305][305],was[305];
vector<int> res,cur;
 
void dfs(int x){
	cur.pb(x);
	was[x]=true;
	if(cur.size()>res.size()) res=cur;
	for(int y=0;y<300;y++){
		if(!was[y]&&con[x][y]){
			dfs(y);
		}
	}
	cur.pop_back();
}
 
mt19937 mrand(time(0));
 
vector<int> longest_trip(int n,int d){
	if(d==3){
		vector<int> ans;
		for(int i=0;i<n;i++) ans.pb(i);
		return ans;
	}
	if(d==2){
		for(int i=0;i<300;i++) for(int j=0;j<300;j++) con[i][j]=false;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				con[i][j]=con[j][i]=are_connected({i},{j});
			}
		}
		res={};
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) was[j]=false;
			dfs(i);
		}
		return res;
	}
	vector<int> ord(n);
	iota(ord.begin(),ord.end(),0);
	shuffle(ord.begin(),ord.end(),mrand);
	vector<int> chn1(1,ord.back()),chn2;
	ord.pop_back();
	for(int i:ord){
		if(!chn1.empty()&&!chn2.empty()){
			bool ok1=are_connected({i},chn1),ok2=are_connected({i},chn2);
			if(ok1&&ok2){
				if(are_connected({i},{chn2[0]})) swap(chn1,chn2);
				swap(chn1[0],chn1.back());
				int l=0,r=chn2.size()-1;
				while(l<r){
					int mid=(l+r-1)/2;
					vector<int> qv;
					for(int j=0;j<=mid;j++) qv.pb(chn2[j]);
					if(are_connected({i},qv)) r=mid;
					else l=mid+1;
				}
				swap(chn2[r],chn2[0]);
				chn1.pb(i);
				for(int v:chn2) chn1.pb(v);
				chn2.clear();
				continue;
			}
			if(!ok1) chn2.pb(i);
			if(!ok2) chn1.pb(i);
			continue;
		}	
		bool ok=are_connected({i},chn1);
		if(!ok){
			chn2={i};
			continue;
		}
		if(are_connected({i},{chn1[0]})){
			reverse(chn1.begin(),chn1.end());
			chn1.pb(i);
			continue;
		}
		int l=0,r=(int)chn1.size()-1;
		while(l<r){
			int mid=(l+r+1)/2;
			vector<int> qv;
			for(int j=mid;j<(int)chn1.size();j++) qv.pb(chn1[j]);
			if(are_connected({i},qv)) l=mid; 
			else r=mid-1;
		}
		int p=chn1[l];
		while(chn1.back()!=p){
			int x=chn1.back();
			chn1.pop_back();
			reverse(chn1.begin(),chn1.end());
			chn1.pb(x);
			reverse(chn1.begin(),chn1.end());
		}
		chn1.pb(i);
	}
	return chn1.size()>chn2.size()?chn1:chn2;
}

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