Submission #1059965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059965		parsadox2	Thousands Islands (IOI22_islands)	C++17	24 / 100	33 ms	10332 KiB

islands

#include <bits/stdc++.h>
#include "islands.h"
#include <variant>
#define F first
#define S second
using namespace std;

const int N = 1e5 + 10 , M = 2e5 + 10;
int n , m , dis[N] , st_tim[N] , fn_tim[N] , tim;
vector <pair<int , int>> adj[N];
pair <int , int> par[N] , bh[N];
bool marked[N];

void Dfs(int v)
{
	marked[v] = true;
	st_tim[v] = tim;
	tim++;
	for(auto u : adj[v])
	{
		if(!marked[u.F])
		{
			par[u.F] = make_pair(v , u.S);
			dis[u.F] = dis[v] + 1;
			Dfs(u.F);
		}
		else if(fn_tim[u.F] == 0)
		{
			if(bh[v].F == -1 || dis[bh[v].F] < dis[u.F])
				bh[v] = u;
		}
	}
	fn_tim[v] = tim;
}

vector <int> Solve1(int v)
{
	vector <int> c;
	c.push_back(bh[v].S);
	int now = v;
	while(now != bh[v].F)
	{
		c.push_back(par[now].S);
		now = par[now].F;
	}
	reverse(c.begin() , c.end());
	vector <int> p;
	now = bh[v].F;
	while(now != 0)
	{
		p.push_back(par[now].S);
		now = par[now].F;
	}
	reverse(p.begin() , p.end());
	vector <int> res;
	for(int ty = 0 ; ty < 2 ; ty++)
	{
		for(auto u : p)
			res.push_back(u);
		reverse(p.begin() , p.end());
		for(auto u : c)
			res.push_back(u);
		for(auto u : p)
			res.push_back(u);
		reverse(p.begin() , p.end());
		for(auto u : p)
			res.push_back(u + 1);
		reverse(p.begin() , p.end());
		for(auto u : c)
			res.push_back(u + 1);
		reverse(c.begin() , c.end());
		for(auto u : p)
			res.push_back(u + 1);
		reverse(p.begin() , p.end());
	}
	return res;
}

variant<bool , vector <int>> find_journey(int nn , int mm , vector <int> U , vector <int> V)
{
	n = nn;
	m = mm;
	for(int i = 0 ; i < m ; i++)
		adj[U[i]].push_back({V[i] , i});
	for(int i = 0 ; i < n ; i++)
		bh[i] = make_pair(-1 , -1);
	Dfs(0);
	bool flg = false;
	for(int i = 0 ; i < n ; i++)
	{
		if(bh[i].F > -1)
		{
			flg = true;
			auto res = Solve1(i);
			return res;
		}
	}
	if(!flg)
		return false;
}

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:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^

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