Submission #1060166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060166		parsadox2	Thousands Islands (IOI22_islands)	C++17	5 / 100	16 ms	8796 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++)  if(U[i] <= 2 && V[i] <= 2)
		adj[U[i]].push_back({V[i] , i});
	if(n <= 2)
		return false;
	vector <int> res;
	for(int i = 0 ; i <= 2 ; i++)
		sort(adj[i].begin() , adj[i].end());
	res.push_back(adj[0][0].S);
	res.push_back(adj[1][0].S);
	res.push_back(adj[0][1].S);
	res.push_back(adj[2][0].S);
	res.push_back(adj[1][0].S);
	res.push_back(adj[0][0].S);
	res.push_back(adj[2][0].S);
	res.push_back(adj[0][1].S);
	return res;
}

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