제출 #1240963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240963		nikulid	수천개의 섬 (IOI22_islands)	C++20	8.40 / 100	24 ms	12104 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);
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];
			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];
			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)return true;
	else return false;

}

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