oj.uz

Submission #148869

# Submission time Handle Problem Language Result Execution time Memory
148869 2019-09-01T05:17:29 Z Welcome to osu!(#3734, easrui, CodePlatina, jhwest2) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 226 ms 7932 KB 
#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(F[S[M - i]], F[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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 7908 KB Output is correct
2 Correct 190 ms 7908 KB Output is correct
3 Correct 181 ms 7908 KB Output is correct
4 Correct 186 ms 7908 KB Output is correct
5 Correct 226 ms 7932 KB Output is correct
6 Correct 181 ms 7908 KB Output is correct
7 Correct 187 ms 7908 KB Output is correct
8 Correct 210 ms 7908 KB Output is correct
9 Correct 195 ms 7908 KB Output is correct
10 Correct 185 ms 7912 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

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