Submission #1236536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236536		MuhammadSaram	Thousands Islands (IOI22_islands)	C++20	0 / 100	1096 ms	8008 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 1;

map<int,vector<int>> nei[M];
vector<int> rev[M];
bool del[M];
set<int> se;
int par[M], id[M], vis[M], r;

void rem()
{
	int x=*se.begin();se.erase(x);
	del[x]=1;
	for (auto i:rev[x])
	{
		nei[i].erase(x);
		if (nei[i].empty()) se.insert(i);
	}
}

vector<int> cyc[2], pre[2];

void dfs(int u, int o)
{
	vis[u]=1;
	for (auto [i,v1]:nei[u])
		for (int x:v1)
		{
			if (cyc[o].size()) return;
			if (!vis[i])
				par[i]=u, id[u]=x, dfs(i,o);
			else if(vis[i]==1)
			{
				int v=u;
				while (v!=i)
					cyc[o].push_back(id[v]), v=par[v];
				reverse(cyc[o].begin(), cyc[o].end());
				cyc[o].push_back(x);
				v=i;
				while (v!=r)
					pre[o].push_back(id[v]), v=par[v];
				reverse(pre[o].begin(),pre[o].end());
			}
		}
	vis[u]=2;
}

bool eq(vector<int> v, vector<int> v1)
{
	sort(v.begin(), v.end());
	sort(v1.begin(), v1.end());
	return v==v1;
}

variant<bool, vector<int>> find_journey(int n, int m, vector<int> U, vector<int> V)
{
	for (int i=0;i<m;i++)
		rev[V[i]].push_back(U[i]),nei[U[i]][V[i]].push_back(i);
	for (int i=0;i<n;i++)
		if (nei[i].empty()) se.insert(i);
	vector<int> v,ans;
	int cur=0;
	while (1)
	{
		while (!se.empty())
			rem();
		if (del[cur] or nei[cur].empty())
			return false;
		if (nei[cur].size()==1)
			v.push_back(nei[cur].begin()->second[0]), cur=nei[cur].begin()->first,
			se.insert(cur),rem();
		if (se.empty()) break;
	}
	vis[cur]=1, r=cur;
	for (auto [i,v1]:nei[cur])
		for (int x:v1)
			par[i]=cur, id[i]=x;
	auto it=nei[cur].begin();
	dfs(it->first,0);it++;
	dfs(it->first,1);
	ans=v;
	if (eq(cyc[0], cyc[1]))
	{
		for (int i:pre[0]) ans.push_back(i);
		for (int i:cyc[0]) ans.push_back(i);
		reverse(pre[0].begin(), pre[0].end());
		for (int i:pre[0]) ans.push_back(i);
		for (int i:pre[1]) ans.push_back(i);
		reverse(cyc[1].begin(), cyc[1].end());
		for (int i:cyc[1]) ans.push_back(i);
		reverse(pre[1].begin(), pre[1].end());
		for (int i:pre[1]) ans.push_back(i);
	}
	else
	{
		for (int i:pre[0]) ans.push_back(i);
		for (int i:cyc[0]) ans.push_back(i);
		reverse(pre[0].begin(), pre[0].end());
		for (int i:pre[0]) ans.push_back(i);
		
		for (int i:pre[1]) ans.push_back(i);
		for (int i:cyc[1]) ans.push_back(i);
		reverse(pre[1].begin(), pre[1].end());
		for (int i:pre[1]) ans.push_back(i);
		
		reverse(pre[0].begin(), pre[0].end());
		for (int i:pre[0]) ans.push_back(i);
		reverse(cyc[0].begin(), cyc[0].end());
		for (int i:cyc[0]) ans.push_back(i);
		reverse(pre[0].begin(), pre[0].end());
		for (int i:pre[0]) ans.push_back(i);
		
		reverse(pre[1].begin(), pre[1].end());
		for (int i:pre[1]) ans.push_back(i);
		reverse(cyc[1].begin(), cyc[1].end());
		for (int i:cyc[1]) ans.push_back(i);
		reverse(pre[1].begin(), pre[1].end());
		for (int i:pre[1]) ans.push_back(i);
	}
	reverse(v.begin(), v.end());
	for (int i:v) ans.push_back(i);
	return ans;
}

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