제출 #954929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954929		n1k	Thousands Islands (IOI22_islands)	C++17	10.15 / 100	112 ms	14680 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<array<int, 2>>> g;
vector<map<int, int>> connected;
vector<int> color, par, nett;

int x, y;

bool dfs(int u, int p){
	par[u] = p;

	if(color[u]==2) return false;

	color[u] = 1;

	if(nett[u]){
		return true;
	}

	for(auto [v, e]:g[u]){
		if(v==p)
			continue;
		if(color[v]==1){
			x = v;
			y = u;
			return true;
		}
		if(dfs(v, u)){
			return true;
		}
	}

	color[u] = 2;

	return false;
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
	g.assign(N, {});
	connected.assign(N, {});
	color.assign(N, {});
	par.assign(N, {});
	nett.assign(N, {});

	for(int i=0; i<M; i++){
		if(not connected[U[i]][V[i]]){
			g[U[i]].push_back({V[i], i});
		}

		connected[U[i]][V[i]]++;

		if(connected[U[i]][V[i]]>=2 and connected[V[i]][U[i]]>=1){
			nett[U[i]]=1;
		}
		if(connected[U[i]][V[i]]>=1 and connected[V[i]][U[i]]>=2){
			nett[V[i]]=1;
		}
	}

	return dfs(0, -1);
}

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