Submission #635204

#	Time	Username	Problem	Language	Result	Execution time	Memory
635204		youngyojun	Thousands Islands (IOI22_islands)	C++17	29 / 100	1087 ms	7204 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(G[S].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];
	dead.reset();

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

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

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:64:24: warning: unused variable 'cnt' [-Wunused-variable]
   64 |   int pve = -1, v = S, cnt = 0;
      |                        ^~~

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