제출 #635218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635218		youngyojun	수천개의 섬 (IOI22_islands)	C++17	100 / 100	133 ms	16744 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], T[MAXN];

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

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

	vector<int> PV;
	int S = 0;

	vector<int> ZV;
	for(int i = N; i--;) if(!oc[i]) ZV.eb(i);
	while(1 == oc[S] || !ZV.empty()) {
		if(1 == oc[S]) {
			int e = *find_if(allv(G[S]), [&](int e){ return !dead[e]; });
			PV.eb(e);
			dead[e] = true;
			oc[S] = 0;
			ZV.eb(S);
			S = B[e];
		}

		int i = ZV.back(); ZV.pop_back();

		for(int e : T[i]) {
			dead[e] = true;
			int v = A[e];
			if(!--oc[v]) ZV.eb(v);
		}
	}

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

	if(G[S].empty()) return false;

	for(int i = N; i--;)
		G[i].resize(i == S ? 2 : 1);
	for(int i = M; i--;) A[i] ^= B[i];

	dead.reset();

	vector<int> CV;
	int pve = -1, v = S;
	do {
		for(int e : G[v]) if(e != pve) {
			CV.eb(e);
			pve = e;
			dead[e] = !dead[e];
			delv(G[v], e);
			v ^= A[e];
			G[v].eb(e);
			break;
		}
	} while(v != S || dead.any());

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

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