제출 #776622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776622		SanguineChameleon	수천개의 섬 (IOI22_islands)	C++17	31 / 100	1137 ms	909924 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
vector<pair<int, int>> adj[maxN];
int flag[maxN];
pair<int, int> par[maxN];
vector<int> cycle1;
vector<int> cycle2;
vector<int> suf;

void dfs(int u) {
	if (!cycle1.empty()) {
		return;
	}
	flag[u] = 2;
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (flag[v] == 2) {
			cycle1.push_back(id);
			cycle2.push_back(id ^ 1);
			while (u != v) {
				cycle1.push_back(par[u].second);
				cycle2.push_back(par[u].second ^ 1);
				u = par[u].first;
			}
			reverse(cycle1.begin(), cycle1.end());
			reverse(cycle2.begin(), cycle2.end());
			while (u != 0) {
				suf.push_back(par[u].second);
				u = par[u].first;
			}
			return;
		}
		if (flag[v] == 0) {
			par[v] = {u, id};
			dfs(v);
		}
	}
	flag[u] = 1;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	if (N == 2) {
		vector<int> left;
		vector<int> right;
		for (int i = 0; i < M; i++) {
			if (U[i] == 0) {
				left.push_back(i);
			}
			else {
				right.push_back(i);
			}
		}
		if ((int)left.size() < 2 || right.empty()) {
			return false;
		}
		int A = left[0];
		int B = right[0];
		int C = left[1];
		return vector<int>({A, B, C, A, B, C});
	}
	bool sub3 = (M % 2 == 0);
	bool sub4 = (M % 2 == 0);
	for (int i = 0; i < M; i += 2) {
		sub3 &= (U[i] == V[i + 1] && V[i] == U[i + 1]);
		sub4 &= (U[i] == U[i + 1] && V[i] == V[i + 1]);
	}
	if (sub3) {
		for (int i = 0; i < M; i += 2) {
			adj[U[i]].emplace_back(V[i], i);
			adj[V[i]].emplace_back(U[i], i ^ 1);
		}
		if (adj[0].empty()) {
			return false;
		}
		if ((int)adj[0].size() >= 2) {
			int A = adj[0][0].second;
			int B = A ^ 1;
			int C = adj[0][1].second;
			int D = C ^ 1;
			return vector<int>({A, B, C, D, B, A, D, C});
		}
		int prv = 0;
		int cur = adj[0][0].first;
		vector<int> res = {adj[0][0].second};
		while (true) {
			if ((int)adj[cur].size() == 1) {
				return false;
			}
			if ((int)adj[cur].size() >= 3) {
				int A = -1;
				int B = -1;
				int C = -1;
				int D = -1;
				for (auto e: adj[cur]) {
					int nxt = e.first;
					int id = e.second;
					if (nxt != prv) {
						if (A == -1) {
							A = id;
							B = id ^ 1;
						}
						else if (C == -1) {
							C = id;
							D = id ^ 1;
						}
					}
				}
				vector<int> mid({A, B, C, D, B, A, D, C});
				vector<int> suf(res.rbegin(), res.rend());
				res.insert(res.end(), mid.begin(), mid.end());
				res.insert(res.end(), suf.begin(), suf.end());
				return res;
			}
			for (auto e: adj[cur]) {
				int nxt = e.first;
				int id = e.second;
				if (nxt != prv) {
					prv = cur;
					cur = nxt;
					res.push_back(id);
					break;
				}
			}
		}
		return false;
	}
	if (sub4) {
		for (int i = 0; i < M; i += 2) {
			adj[U[i]].emplace_back(V[i], i);
		}
		dfs(0);
		if (cycle1.empty()) {
			return false;
		}
		vector<int> res(suf.rbegin(), suf.rend());
		res.insert(res.end(), cycle1.begin(), cycle1.end());
		res.insert(res.end(), cycle2.begin(), cycle2.end());
		res.insert(res.end(), cycle1.rbegin(), cycle1.rend());
		res.insert(res.end(), cycle2.rbegin(), cycle2.rend());
		res.insert(res.end(), suf.begin(), suf.end());
		return res;
	}
	int A = -1;
	int B = -1;
	int C = -1;
	int D = -1;
	for (int i = 0; i < M; i++) {
		if (U[i] == 0 && V[i] == 1) {
			A = i;
		}
		if (U[i] == 1 && V[i] == 0) {
			B = i;
		}
		if (U[i] == 0 && V[i] == 2) {
			C = i;
		}
		if (U[i] == 2 && V[i] == 0) {
			D = i;
		}
	}
	return vector<int>({A, B, C, D, B, A, D, C});
}

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