oj.uz

Submission #760113

# Submission time Handle Problem Language Result Execution time Memory
760113 2023-06-17T07:59:46 Z denniskim Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 184 ms 34008 KB 
#include "island.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n, m;
ll a[100010];
ll pa[100010], ra[100010];
vector<pll> vec[100010];
ll spa[100010][21], mspa[100010][21];
ll dep[100010];

ll ffind(ll here)
{
	if(here == pa[here])
		return pa[here];
	
	return pa[here] = ffind(pa[here]);
}

void uunion(ll X, ll Y)
{
	X = ffind(X);
	Y = ffind(Y);
	
	if(X == Y)
		return;
	
	if(ra[X] < ra[Y])
		pa[X] = Y;
	else if(ra[X] > ra[Y])
		pa[Y] = X;
	
	else
	{
		pa[X] = Y;
		ra[Y]++;
	}
}

void dfs(ll here, ll p)
{
	for(auto &i : vec[here])
	{
		if(i.fi == p)
			continue;
		
		dep[i.fi] = dep[here] + 1;
		spa[i.fi][0] = here;
		mspa[i.fi][0] = i.se;
		dfs(i.fi, here);
	}
}

void Init(ll K, vector<ll> F, vector<ll> S, vector<ll> E)
{
	n = (ll)F.size();
	m = (ll)S.size();
	
	for(ll i = 0 ; i < n ; i++)
		a[i] = F[i];
	
	for(ll i = 0 ; i < n ; i++)
		pa[i] = i;
	
	for(ll i = m - 1 ; i >= 0 ; i--)
	{
		if(ffind(F[S[i]]) == ffind(F[E[i]]))
			continue;
		
		uunion(F[S[i]], F[E[i]]);
		vec[F[S[i]]].push_back({F[E[i]], i + 1});
		vec[F[E[i]]].push_back({F[S[i]], i + 1});
	}
	
	dfs(0, -1);
	
	for(ll i = 1 ; i <= 20 ; i++)
	{
		for(ll j = 0 ; j < n ; j++)
		{
			spa[j][i] = spa[spa[j][i - 1]][i - 1];
			mspa[j][i] = min(mspa[j][i - 1], mspa[spa[j][i - 1]][i - 1]);
		}
	}
}

ll Separate(ll A, ll B)
{
	ll ans = 987654321;
	
	if(dep[A] < dep[B])
		swap(A, B);
	
	ll cha = dep[A] - dep[B];
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(cha >= (1LL << i))
		{
			cha -= (1LL << i);
			ans = min(ans, mspa[A][i]);
			A = spa[A][i];
		}
	}
	
	if(A == B)
		return ans;
	
	for(ll i = 20 ; i >= 0 ; i--)
	{
		if(spa[A][i] != spa[B][i])
		{
			ans = min(ans, mspa[A][i]);
			ans = min(ans, mspa[B][i]);
			A = spa[A][i];
			B = spa[B][i];
		}
	}
	
	ans = min(ans, mspa[A][0]);
	ans = min(ans, mspa[B][0]);
	
	return ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 29792 KB Output is correct
2 Correct 166 ms 34008 KB Output is correct
3 Correct 157 ms 34004 KB Output is correct
4 Correct 136 ms 33912 KB Output is correct
5 Correct 184 ms 33968 KB Output is correct
6 Correct 138 ms 33976 KB Output is correct
7 Correct 134 ms 33936 KB Output is correct
8 Correct 161 ms 34004 KB Output is correct
9 Correct 141 ms 33972 KB Output is correct
10 Correct 132 ms 33988 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -