제출 #150390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150390		본인 하지만 안 어림 ㅋㅋ (#200)	갈라파고스 여행 (FXCUP4_island)	C++17	31 / 100	352 ms	26792 KiB

island

#include <bits/stdc++.h>
using namespace std;

#include "island.h"

int unf[100010];
int root(int x)
{
    return unf[x] == x ? x : (unf[x] = root(unf[x]));
}
bool merge(int x, int y)
{
    x = root(x);
    y = root(y);
    if(x == y)
        return 0;
    unf[x] = y;
    return 1;
}

struct edg
{
    int x, w;
};

vector<edg> adj[100010];

int par[100010][18];
int mem[100010][18];
int dep[100010];
void f(int x, int p)
{
    par[x][0] = p;
    for(int i = 1; i < 18; i++)
    {
        par[x][i] = par[par[x][i - 1]][i - 1];
        mem[x][i] = min(mem[x][i - 1], mem[par[x][i - 1]][i - 1]);
    }

    for(edg e : adj[x])
    {
        if(e.x == p)
            continue;

        mem[e.x][0] = e.w;
        dep[e.x] = dep[x] + 1;
        f(e.x, x);
    }
}

int lca(int x, int y)
{
    if(dep[y] > dep[x])
        swap(x, y);

    int t = dep[x] - dep[y];
    for(int i = 0; i < 18; i++)
        if(t & (1 << i))
            x = par[x][i];

    if(x == y)
        return x;

    for(int i = 17; i >= 0; i--)
    {
        if(par[x][i] != par[y][i])
        {
            x = par[x][i];
            y = par[y][i];
        }
    }

    assert(x != y && par[x][0] == par[y][0]);
    return par[x][0];
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int N = F.size(), M = S.size();

    assert(K == N);

    for(int i = 0; i < N; i++)
        unf[i] = i;

    for(int i = M - 1; i >= 0; i--)
    {
        int x = F[S[i]];
        int y = F[E[i]];

        if(merge(x, y))
        {
            adj[x].push_back({ y, i + 1 });
            adj[y].push_back({ x, i + 1 });
        }
    }

    mem[0][0] = 1e9;
    f(0, 0);
}

int Separate(int x, int y){

    int z = lca(x, y);
    int r = 1e9;

    {
        int d = dep[x] - dep[z];
        int c = x;

        for(int i = 0; i < 18; i++)
        {
            if(d & (1 << i))
            {
                r = min(r, mem[c][i]);
                c = par[c][i];
            }
        }
    }
    {
        int d = dep[y] - dep[z];
        int c = y;

        for(int i = 0; i < 18; i++)
        {
            if(d & (1 << i))
            {
                r = min(r, mem[c][i]);
                c = par[c][i];
            }
        }
    }

	return r;
}

• Subtask 1: 31 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30