Submission #1240977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240977		nikulid	Thousands Islands (IOI22_islands)	C++20	0 / 100	1151 ms	1058788 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

// below are used to find the trip itself (path in terms of nodes)
vector<vector<int>> adj(1000);
vector<bool> visitted(1000, 0), been(1000, 0);
vector<int> goes(1000, -1), from(1000, -1);
int cycle_found=0;

// below are used to find the canoes to do the trip (path in terms of canoes)
vector<vector<int>> adjA(1000, vector<int>(1000, -1));
vector<vector<int>> adjB(1000, vector<int>(1000, -1));

void dfs(int node){
	if(cycle_found)return;
	been[node]=1;
	visitted[node]=1;
	for(int i=0; i<adj[node].size(); i++){
		if(!been[adj[node][i]]){
			// un-explored node...
			goes[node] = adj[node][i];
			from[adj[node][i]] = node;
			dfs(adj[node][i]);
		} else if(been[adj[node][i]] && visitted[adj[node][i]]){
			// cycle found!!!
			cycle_found = node+1;
			goes[node] = adj[node][i];
			from[adj[node][i]] = node;
			return;
		}
		// otherwise, we have
		// been[]=1 && visitted[]=0
		// which means we've exhausted all options with this node already.
	}
	visitted[node]=0;
	return;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	/*
	   adj[u] = {..., v, ...}

	   adjA[u][v] = first canoe for u->v
	   adjB[u][v] = second canoe for u->v

	   ( trip[i] = {node to travel to, 0(A)/1(B)/2(reverse,A)/3(reverse,B)}
	*/

	int u,v;
	for(int i=0; i<M; i++){
		u=U[i]; v=V[i];
		if(adjA[u][v] == -1){
			adj[u].pb(v);
			adjA[u][v] = i;
		} else{
			adjB[u][v] = i;
		}
	}
	dfs(0);
	if(cycle_found){
		// now to find the canoes... (easy part? right? right???)
		vector<int> answer;
		
		// 0 -> cycle_found
		int cur=0;
		while(cur != cycle_found){
			answer.pb(adjA[cur][goes[cur]]);
			cur = goes[cur];
		}

		// cycle_found -> cycle_found (forwards) x2
		answer.pb(adjA[cur][goes[cur]]);
		cur = goes[cur];
		while(cur != cycle_found){
			answer.pb(adjA[cur][goes[cur]]);
			cur = goes[cur];
		}
		answer.pb(adjB[cur][goes[cur]]);
		cur = goes[cur];
		while(cur != cycle_found){
			answer.pb(adjB[cur][goes[cur]]);
			cur = goes[cur];
		}

		// cycle_found <- cycle_found (backwards) x2
		answer.pb(adjA[from[cur]][cur]);
		cur = from[cur];
		while(cur != cycle_found){
			answer.pb(adjA[from[cur]][cur]);
			cur = from[cur];
		}
		
		answer.pb(adjB[from[cur]][cur]);
		cur = from[cur];
		while(cur != cycle_found){
			answer.pb(adjB[from[cur]][cur]);
			cur = from[cur];
		}

		// 0 <- cycle_found (backwards)
		while(cur != 0){
			answer.pb(adjA[from[cur]][cur]);
			cur = from[cur];
		}
		return answer;

	}
	else return false;

}

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