제출 #1235923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235923		MuhammadSaram	수천개의 섬 (IOI22_islands)	C++20	0 / 100	1114 ms	1060564 KiB

islands

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

using namespace std;

const int M = 1e5 + 1;

set<pair<int,int>> rev[M],nei[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,j]:rev[x])
	{
		nei[i].erase({x,j});
		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,x]:nei[u])
	{
		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]].insert({U[i],i}),nei[U[i]].insert({V[i],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] && nei[cur].empty())
			return false;
		if (nei[cur].size()==1)
			v.push_back(nei[cur].begin()->second), cur=nei[cur].begin()->first,
			se.insert(cur),rem();
		if (se.empty()) break;
	}
	vis[cur]=1, r=cur;
	for (auto [i,x]:nei[cur])
		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