oj.uz

Submission #149692

# Submission time Handle Problem Language Result Execution time Memory
149692 2019-09-01T06:58:41 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 261 ms 26516 KB 
#include "island.h"
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100100;
const int BSIZE = 500;
const int NBUCK = 210;

int N, M;
int fval[MAXN];
int floc[MAXN];

int par[MAXN];
vector <int> guys[MAXN];
vector <int> dists[MAXN];

int ndist[MAXN];
int oloc[MAXN];
int nmin[MAXN][20];
int nhun[MAXN];

void uni (int left, int right, int now)
{
    left = par[left];
    right = par[right];
    if (left == right) return;
    if (guys[left].size() < guys[right].size()) swap (left, right);

    dists[left].push_back(now);
    for (int guy : guys[right])
    {
        guys[left].push_back(guy);
        par[guy] = left;
    }
    for (int dist : dists[right])
    {
        dists[left].push_back(dist);
    }
    guys[right].clear();
    dists[right].clear();
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	N = F.size(), M = S.size();
    for (int i = 0; i < N; i++)
    {
        fval[i] = F[i];
        floc[fval[i]] = i;
    }

    for (int i = 0; i < N; i++)
    {
        guys[i].clear();
        dists[i].clear();
        guys[i].push_back(i);
        par[i] = i;
    }

    for (int i = M - 1; i >= 0; i--)
    {
        int l = S[i], r = E[i];

        uni (l, r, i + 1);
    }

    int cp = par[0];
    for (int i = 0; i < N; i++)
    {
        if (i < N - 1)
            ndist[i] = dists[cp][i];
        oloc[guys[cp][i]] = i;
    }

    for (int i = 0; i < N; i++)
        nmin[i][0] = ndist[i];
    for (int a = 0; a < 19; a++)
    {
        for (int i = 0; i < N; i++)
        {
            nmin[i][a+1] = nmin[i][a];
            if (i + (1 << a) < N)
                nmin[i][a+1] = min (nmin[i][a], nmin[i+(1<<a)][a]);
        }
    }
}

int gogo (int x, int y)
{
    if (x > y) swap (x, y);
    int np = 31 - __builtin_clz(y - x);
    return min (nmin[x][np], nmin[y-(1<<np)][np]);
}

int Separate(int A, int B)
{
    return gogo (oloc[floc[A]], oloc[floc[B]]);
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 26516 KB Output is correct
2 Correct 229 ms 26212 KB Output is correct
3 Correct 237 ms 26464 KB Output is correct
4 Correct 245 ms 26212 KB Output is correct
5 Correct 201 ms 26340 KB Output is correct
6 Correct 241 ms 26468 KB Output is correct
7 Correct 261 ms 26468 KB Output is correct
8 Correct 228 ms 26464 KB Output is correct
9 Correct 228 ms 26468 KB Output is correct
10 Correct 221 ms 26464 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

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