Submission #1241012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241012		nikulid	Thousands Islands (IOI22_islands)	C++20	0 / 100	4 ms	8516 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, cyclefrom=0;
bool found_a_cycle=false;

// 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(found_a_cycle)return;
	derr<<"dfsing "<<node<<"...\n";
	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 = adj[node][i];
			found_a_cycle=true;
			goes[node] = adj[node][i];
			//from[adj[node][i]] = node;
			cyclefrom = 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(!found_a_cycle)derr<<"no cycle found :(\n";
	if(debug)
	{	
		cerr<<"<--- adj --->\n";
		for(int i=0; i<N; i++){
			cerr<<i<<": ";
			for(int l=0; l<adj[i].size(); l++){
				cerr<<adj[i][l]<<",";
			}cerr<<"\n";
		}

		cerr<<"cyclefrom: "<<cyclefrom<<"\n";

		cerr<<"goes: ";
		for(int i=0; i<N; i++){
			cerr<<goes[i]<<" ";
		}

		cerr<<"\nfrom: ";
		for(int i=0; i<N; i++){
			cerr<<from[i]<<" ";
		}cerr<<"\n\n";
	}		

	if(found_a_cycle){
		derr<<"cycle found @ "<<cycle_found<<"!\n";
		// now to find the canoes... (easy part? right? right???)
		vector<int> answer;
		
		// 0 -> cycle_found
		derr<<"cycle 0...\n";
		int cur=0;
		while(cur != cycle_found){
			answer.pb(adjA[cur][goes[cur]]);
			cur = goes[cur];
		}
		derr<<"cycle 1...\n";
		// 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];
		}
		derr<<"cycle 2... (cur="<<cur<<")\n";
		// cycle_found <- cycle_found (backwards) x2
		//
		//
		//
		answer.pb(adjA[cyclefrom][cur]);
		cur = cyclefrom;
		derr<<"next cur: "<<cur<<"\n";
		while(cur != cycle_found){
			answer.pb(adjA[from[cur]][cur]);
			cur = from[cur];
		}
		
		answer.pb(adjB[cyclefrom][cur]);
		cur = cyclefrom;
		while(cur != cycle_found){
			answer.pb(adjB[from[cur]][cur]);
			cur = from[cur];
		}
		derr<<"cycle 3...\n";
		// 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