Submission #629881

#	Time	Username	Problem	Language	Result	Execution time	Memory
629881		prvocislo	Thousands Islands (IOI22_islands)	C++17	100 / 100	385 ms	33600 KiB

islands

#include "islands.h"
#include <variant>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V) 
{
	vector<set<pair<int, int> > > g(n), gr(n);
	for (int i = 0; i < m; i++)
	{
		g[U[i]].insert({ V[i], i });
		gr[V[i]].insert({ U[i], i });
	}
	queue<int> q;
	for (int i = 0; i < n; i++)
	{
		if (g[i].empty()) q.push(i);
	}
	int vr = 0;
	vector<int> path, ans;
	while (true)
	{
		while (!q.empty())
		{
			int u = q.front();
			q.pop();
			for (pair<int, int> v : gr[u])
			{
				g[v.first].erase({ u, v.second });
				if (g[v.first].empty()) q.push(v.first);
			}
			gr[u].clear();
		}
		if (g[vr].empty()) return false;
		if (g[vr].size() == 1)
		{
			int i = g[vr].begin()->second;
			g[vr].clear();
			gr[V[i]].erase({ U[i], i });
			path.push_back(i);
			ans.push_back(i);
			q.push(vr);
			vr = V[i];
		}
		else break;
	}
	for (int i = 0; i < n; i++)
	{
		if (i == vr) g[i].erase(next(g[i].begin(), 2), g[i].end());
		else if (g[i].size()) g[i].erase(next(g[i].begin()), g[i].end());
	}
	vector<int> rev(m, 0);
	int cnt = 0, lst = -1;
	do
	{
		int i = g[vr].begin()->second;
		g[vr].erase(g[vr].begin());

		if (lst != -1) g[U[lst]].insert({ V[lst],lst });
		lst = i;
		ans.push_back(i);
		vr = V[i];
		swap(U[i], V[i]);

		if (rev[i]) cnt--;
		else cnt++;
		rev[i] ^= 1;

	} while (cnt);
	reverse(path.begin(), path.end());
	for (int i : path) ans.push_back(i);
	return ans;
}

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