oj.uz

Submission #150390

# Submission time Handle Problem Language Result Execution time Memory
150390 2019-09-01T08:18:13 Z 본인 하지만 안 어림 ㅋㅋ(#3569, gs13105, xdoju, gs13068) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 352 ms 26792 KB 
#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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 26724 KB Output is correct
2 Correct 352 ms 26720 KB Output is correct
3 Correct 289 ms 26792 KB Output is correct
4 Correct 328 ms 26724 KB Output is correct
5 Correct 339 ms 26724 KB Output is correct
6 Correct 345 ms 26724 KB Output is correct
7 Correct 329 ms 26724 KB Output is correct
8 Correct 328 ms 26724 KB Output is correct
9 Correct 304 ms 26728 KB Output is correct
10 Correct 318 ms 26724 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -