제출 #635202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635202		youngyojun	수천개의 섬 (IOI22_islands)	C++17	5 / 100	1095 ms	7280 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define delv(V,x) (V).erase(find(allv(V),(x)))
using namespace std;

const int MAXN = 100'055;
const int MAXM = 200'055;

vector<int> G[MAXN];

int oc[MAXN];
bitset<MAXM> dead;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	for(int i = M; i--;) {
		G[V[i]].eb(i);
		oc[U[i]]++;
	}

	{
		vector<int> V;
		for(int i = N; i--;) if(!oc[i]) V.eb(i);

		while(!V.empty()) {
			int i = V.back();
			V.pop_back();

			for(int e : G[i]) {
				dead[e] = true;
				int v = U[e];
				if(!--oc[v]) V.eb(v);
			}
		}
	}

	for(int i = N; i--;) G[i].clear();
	for(int i = M; i--;) if(!dead[i]) G[U[i]].eb(i);

	vector<int> PV;
	int S = 0;

	while(1 == sz(G[S])) {
		int e = G[S][0];
		PV.eb(e);
		G[S].clear();
		S = V[e];
	}

	if(!S && !PV.empty()) return false;

	for(int i = N; i--;) {
		if(i == S) G[i].resize(2);
		else if(!G[i].empty()) G[i].resize(1);
	}

	for(int i = M; i--;) U[i] ^= V[i];

	vector<int> CV;
	{
		int pve = -1, v = S, cnt = 0;
		while(cnt < 4) {
			for(int e : G[v]) if(e != pve) {
				CV.eb(e);
				pve = e;
				delv(G[v], e);
				v = U[e] ^ v;
				G[v].eb(e);
				break;
			}
			if(v == S) cnt++;
		}
	}

	vector<int> r = PV;
	r.insert(r.end(), allv(CV));
	reverse(allv(PV));
	r.insert(r.end(), allv(PV));
	return r;
}

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