Submission #1240924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240924		nikulid	Thousands Islands (IOI22_islands)	C++20	6.75 / 100	1127 ms	687756 KiB

islands

#include "islands.h"
#include <map>
#include <variant>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	vector<int> answer;
	if(N==2){ // subtask 1
		vector<int> A, B;
		for(int i=0; i<M; i++){
			if(U[i]==0 && V[i]==1){
				A.pb(i);
			} else{
				B.pb(i);
			}
		}
		if(A.size()>1 && B.size()>0){
			answer = {A[0], B[0], A[1], A[0], B[0], A[1]};
			return answer;
		} else{
			return false;
		}
	}
	
	// subtask 3 (21 marks)

	
	vector<vector<pair<int, int>>> ns(N);
	// ns[node] = { {canoe1, nextIsland}, {canoe2, nextIsland}, {canoe3, nextIsland}, ...}
	int u,v;
	for(int i=0; i<M; i++){
		u=U[i]; v=V[i];
		ns[u].pb( mp(i,v) );
	}
	
	// simple case (same as subtask 2)
	if(ns[0].size() == 0){
		return false;
	} else if(ns[0].size() > 1){
		int a=ns[0][0].first;
		int b;
		if(a%2==0) b=a+1;
		else b=a-1;
		//int b = ((a%2==0) ? a+1 : a-1);
		int c=ns[0][1].first;
		int d;
		if(c%2==0) d=c+1;
		else d=c-1;
		//int d = ((c%2==0) ? c+1 : c-1);
		answer = {a,b,c,d,b,a,d,c};
		return answer;
	}

	// complex case
	int prevc = ns[0][0].first;
	prevc = (prevc%2 ? prevc-1 : prevc+1);
	int prev = 0;
	int cur = ns[0][0].second;
	vector<int> pretrip = {ns[0][0].first};
	vector<int> trip;
	while(true){
		if(ns[cur].size() <= 1){
			// there is only one canoe that started from this island
			return false;
		} else if(ns[cur].size() == 2){
			// this island is merely part of the pretrip
			if(ns[cur][0].first == prevc){
				prev = cur;
				cur = ns[cur][1].second;
				prevc = ns[cur][1].first;
			} else{
				prev = cur;
				cur = ns[cur][0].second;
				prevc = ns[cur][0].first;
			}
			prevc = (prevc%2 ? prevc-1 : prevc+1);
			pretrip.pb(prevc);
		} else{
			// trip located!

			return true;
		}
	}
			
}

• Subtask 1: 5 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45