Submission #1240953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240953		nikulid	수천개의 섬 (IOI22_islands)	C++20	22.75 / 100	20 ms	5152 KiB

islands

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

#include <iostream>
bool debug=0;
#define derr if(debug)cerr

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;
	
	
	// 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);
		derr<<"simple case!\n";
		answer = {a,b,c,d,b,a,d,c};
		return answer;
	}
	// complex case
	int prevc = ns[0][0].first;
	vector<int> pretrip = {prevc};
	prevc = (prevc%2 ? prevc-1 : prevc+1); // negate it so that prevc is the canoe that would take you right back...
	int cur = ns[0][0].second;
	vector<int> trip;
	while(true){
		derr<<"$ cur: "<<cur<<"\n";
		if(ns[cur].size() == 1){
			// there is only one canoe that started from this island
			return false;
		} else if(ns[cur].size() == 2){
			derr<<"part of pretrip...\n";
			// this island is merely part of the pretrip
			if(ns[cur][0].first == prevc){
				prevc = ns[cur][1].first;
				cur = ns[cur][1].second;
			} else{
				prevc = ns[cur][0].first;
				cur = ns[cur][0].second;
			}
			pretrip.pb(prevc);
			derr<<"travelling with canoe "<<prevc<<". ";
			prevc = (prevc%2 ? prevc-1 : prevc+1);
			derr<<"now we should avoid canoe "<<prevc<<"!\n";
		} else{
			// trip located!
			int a,b,c,d;
			if(ns[cur][0].first == prevc){
				a = ns[cur][1].first;
				c = ns[cur][2].first;
			} else if(ns[cur][1].first == prevc){
				a = ns[cur][0].first;
				c = ns[cur][2].first;
			} else{
				a = ns[cur][0].first;
				c = ns[cur][1].first;
			}
			if(a%2==0) b = a+1;
			else b = a-1;
			if(c%2==0) d = c+1;
			else d = c-1;
			trip = {a,b,c,d,b,a,d,c};
			for(int e:pretrip){
				answer.pb(e);
			}
			for(int e:trip){
				answer.pb(e);
			}
			for(int i=pretrip.size()-1; i>-1; i--){
				answer.pb(pretrip[i]);
			}
			return answer;
		}
	}
			
}

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