Submission #1233728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233728		nikulid	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	4 ms	408 KiB

longesttrip

#include "longesttrip.h"
#include <queue>
#include <iostream>
#include <assert.h>

using namespace std;

#define pb push_back

vector<int> longest_trip(int n, int d){
	vector<int> ans;
	if(d==2){
		// surely there still exists a round trip...
		// why is this screaming linked list :(
		vector<int> starts;
		if(!are_connected({0}, {n-1})){
			starts.pb(0);
		}
		for(int i=1; i<n; i++){
			if(!are_connected({i-1}, {i})){
				starts.pb(i);
			}
		}
		if(starts.size()==0){
			d=3; // go do the easy case (0,1,2,...)
		} else{
			// we certainly have breaks somewhere.
			starts.pb(starts[0]+n);
			bool forwards=false;
			for(int j=0; j<starts.size()-1; j++){				
				forwards = !forwards;
				if(forwards){
					// forwards
					for(int i=starts[j]; i<starts[j+1]; i++){
						ans.pb(i%n);
					}
				} else{
					// backwards
					for(int i=starts[j+1]-1; i>starts[j]-1; i--){
						ans.pb(i%n);
					}
				}
			}
		}

	}
	if(d==3){
		for(int i=0; i<n; i++){
			ans.pb(i);
		}
	}

	if(d==1){
		// the boss fight
		vector<int> link(n, -1);
		int start1, start2, end1, end2;
		int a,b,c;
		queue<int> q;
		a=are_connected({0}, {1});
		b=are_connected({1}, {2});
		c=are_connected({0}, {2});

		if(a){
			start1=0;
			link[0]=1;
			end1=1;
		} else if(b){
			start1=1;
			link[1]=2;
			end1=2;
		} else if(c){
			start1=0;
			link[0]=2;
			end1=2;
		}
		for(int i=0; i<n; i++){
			if(i!=start1 && i!=end1){
				q.push(i);
			}
		}
		a=-1;b=-1;c=-1;
		start2=-1;end2=-1;


		while(!q.empty()){
			// a
			a=end1;
			// b
			if(start2==-1){
				b=q.front();
				q.pop();
				start2=b;
				end2=b;
			}
			// c
			if(c==-1){
				c=q.front();
				q.pop();
			}
			cerr<<"#(a,b,c)"<<a<<","<<b<<","<<c<<"\n";

			assert(a!=b);
			assert(b!=c);
			assert(a!=c);
			
			if(are_connected({a}, {b})){
				// a-b (join the lists)
				link[a]=b;
				end1=end2;
				start2=-1;
				end2=-1;
			} else if(are_connected({a}, {c})){
				// a-c (go to list1)
				end1=c;
				link[a]=c;
				c=-1;
			} else if(1==1 || are_connected({b}, {c})){
				// b-c (go to list2)
				start2=c;
				link[c]=b;
				c=-1;
			}
		}
		int cur=start1;
		int siz=1;
		vector<int> ans1={start1};
		while(link[cur] != -1){
			cur = link[cur];
			ans1.pb(cur);
		}
		if(start2==-1){
			return ans1;
		} // else...
		cur=start2;
		vector<int> ans2={start2};
		while(link[cur] != -1){
			cur = link[cur];
			ans2.pb(cur);
		}
		if(ans1.size() >= ans2.size()){
			return ans1;
		} else{
			return ans2;
		}
		

	}
	return ans;
}

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