제출 #1060152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060152		parsadox2	수천개의 섬 (IOI22_islands)	C++17	6.75 / 100	25 ms	10116 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});
	if(adj[0].size() < 2 || adj[1].size() < 1)
		return false;
	vector <int> res;
	for(int i = 0 ; i < 2 ; i++)
	{
		res.push_back(adj[0][0].S);
		res.push_back(adj[1][0].S);
		res.push_back(adj[0][1].S);
	}
	return res;
}

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