Submission #148858

#	Time	Username	Problem	Language	Result	Execution time	Memory
148858		Welcome to osu! (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	173 ms	7904 KiB

island

#include "island.h"

int M;

struct nd
{
    int f_par;
    int s_par;
    int tm;

    int get(int t)
    {
        if(t >= tm) return s_par;
        else return f_par;
    }
};

nd uf[101010];
int rnk[101010];

int fnd(int x, int t)
{
    int par = uf[x].get(t);
    if(x == par) return x;
    else return fnd(par, t);
}

void uni(int x, int y, int t)
{
    x = fnd(x, t);
    y = fnd(y, t);
    if(x == y) return;
    else
    {
        if(rnk[x] == rnk[y])
        {
            ++rnk[x];
            uf[y].s_par = x;
            uf[y].tm = t;
        }

        else if(rnk[x] > rnk[y])
        {
            uf[y].s_par = x;
            uf[y].tm = t;
        }

        else
        {
            uf[x].s_par = y;
            uf[x].tm = t;
        }
    }
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int N = F.size(); M = S.size();
	for(int i = 0; i < N; ++i)
    {
        uf[i].f_par = i;
        uf[i].s_par = -1;
        uf[i].tm = M + 1;
    }

    for(int i = 1; i <= M; ++i)
    {
        uni(S[M - i], E[M - i], i);
    }
}

int Separate(int A, int B){
	int s = 0, t = M;
	while(s + 1 < t)
    {
        int mid = (s + t) >> 1;
        if(fnd(A, mid) == fnd(B, mid)) t = mid;
        else s = mid;
    }
    return M - s;
}

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