Submission #1060000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060000		parsadox2	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	24 ms	9560 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> p;
	int now = v;
	while(now != 0)
	{
		p.push_back(par[now].S);
		now = par[now].F;
	}
	reverse(p.begin() , p.end());
	vector <int> vec;
	for(auto u : adj[v])  if(u.S != (par[v].S ^ 1))
		vec.push_back(u.S);
	vector <int> res;
	for(auto u : p)
		res.push_back(u);
	reverse(p.begin() , p.end());
	res.push_back(vec[0]);
	res.push_back((vec[0] ^ 1));
	res.push_back(vec[1]);
	res.push_back((vec[1] ^ 1));
	res.push_back((vec[0] ^ 1));
	res.push_back(vec[0]);
	res.push_back((vec[1] ^ 1));
	res.push_back(vec[1]);
	for(auto u : p)
		res.push_back(u);
	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);
	par[0] = make_pair(-1 , -1);
	Dfs(0);
	bool flg = false;
	for(int i = 0 ; i < n ; i++)
	{
		if(i == 0 && adj[i].size() > 1)
		{
			flg = true;
			auto res = Solve1(i);
			return res;
		}
		if(marked[i] && adj[i].size() > 2)
		{
			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:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^

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