제출 #1232570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232570		nicolo_010	수천개의 섬 (IOI22_islands)	C++20	0 / 100	2 ms	840 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;
template <typename T>
using v = vector<T>;
using pii = pair<int, int>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<int> anterior;
v<v<int>> adj;
v<int> vis;
v<int> cycle;
int beg;

void dfs(int n, int p=-1) {
	if (beg != -1) return;
	//cout << n << endl;
	vis[n] = 1;
	anterior[n] = p;
	for (auto x : adj[n]) {
		if (beg != -1) return;
		//cout << x << " " << beg << " " << vis[x] << endl;
		if (vis[x] == 1) {
			cycle.clear();
			int u = n;
			beg = x;
			while (anterior[u] != -1) {
				cycle.push_back(u);
				u = anterior[u];
			}
			cycle.push_back(u);
			reverse(cycle.begin(), cycle.end());
			return;
		}
		if (!vis[x]) {
			dfs(x, n);
		}
	}
	vis[n] == 2;
}

std::variant<bool, v<int>> find_journey(int N, int M, v<int> U, v<int> V) {
	int n = N;
	adj.resize(n);
	anterior.resize(n);
	vis.assign(n, 0);
	beg = -1;
	map<pii, v<int>> mp;
	rep(i, 0, M) {
		if (!mp.count({U[i], V[i]})) adj[U[i]].push_back(V[i]);
		mp[{U[i], V[i]}].push_back(i);
	}
	dfs(0);
	if (beg == -1) return false;
	else {
		v<int> ans;
		int idx;
		rep(i, 0, (int)cycle.size()) {
			if (cycle[i] == beg) {
				idx = i;
				break;
			}
			ans.push_back(mp[{cycle[i], cycle[i+1]}][0]);
		}		
		v<int> rev = ans;
		reverse(rev.begin(), rev.end());
		v<int> first;
		rep(i, idx, (int)cycle.size()) {
			int a, b;
			a = cycle[i];
			if (i == (int)cycle.size()-1) b = beg;
			else b = cycle[i+1];
			first.push_back(mp[{a, b}][0]);
		}
		for (auto x : first) ans.push_back(x);
		reverse(first.begin(), first.end());
		v<int> second;
		rep(i, idx, (int)cycle.size()) {
			int a, b;
			a = cycle[i];
			if (i == (int)cycle.size()-1) b = beg;
			else b = cycle[i+1];
			second.push_back(mp[{a, b}][1]);
		}
		for (auto x : second) ans.push_back(x);
		reverse(second.begin(), second.end());
		for (auto x : first) ans.push_back(x);
		for (auto x : second) ans.push_back(x);
		for (auto x : rev) ans.push_back(x);
		return ans;
	}
}

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