oj.uz

Submission #150101

# Submission time Handle Problem Language Result Execution time Memory
150101 2019-09-01T07:43:11 Z USA1(#3634, ecnerwala, scott_wu, ksun48) Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 1871 ms 68836 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];
vector <int> floc[MAXN];

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

int ndist[MAXN];
int oloc[MAXN];
int nmin[MAXN][22];

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();
}

int nbig;
vector <int> bfinch;
int bloc[MAXN];
int bdist[NBUCK];
int bbest[NBUCK][MAXN];

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]].push_back(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;
    }

    nbig = 0;
    for (int i = 0; i <= N; i++)
    {
        if (!floc[i].size()) continue;

        for (int j = 0; j < floc[i].size(); j++)
            floc[i][j] = oloc[floc[i][j]];
        sort (floc[i].begin(), floc[i].end());

        if (floc[i].size() >= BSIZE)
        {
            bfinch.push_back(i);
            bloc[i] = nbig;
            nbig++;
        }
        else
            bloc[i] = -1;
    }

    for (int i = 0; i < nbig; i++)
    {
        bdist[i] = -1;
        for (int j = 0; j < MAXN; j++)
            bbest[i][j] = -1;
    }
    for (int i = 0; i < N; i++)
    {
        int ccolor = fval[guys[cp][i]];
        for (int j = 0; j < nbig; j++)
            bbest[j][ccolor] = max (bbest[j][ccolor], bdist[j]);
        if (bloc[ccolor] != -1)
            bdist[bloc[ccolor]] = 1e9;

        if (i == N - 1) continue;
        for (int j = 0; j < nbig; j++)
            bdist[j] = min (bdist[j], ndist[i]);
    }
    for (int i = 0; i < nbig; i++)
    {
        bdist[i] = -1;
    }

    for (int i = N - 1; i >= 0; i--)
    {
        int ccolor = fval[guys[cp][i]];
        for (int j = 0; j < nbig; j++)
            bbest[j][ccolor] = max (bbest[j][ccolor], bdist[j]);
        if (bloc[ccolor] != -1)
            bdist[bloc[ccolor]] = 1e9;

        if (i == 0) continue;
        for (int j = 0; j < nbig; j++)
            bdist[j] = min (bdist[j], ndist[i-1]);        
    }

    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)
{
    //cout << "go " <<  x << " " << y << endl;
    if (x > y) swap (x, y);
    if (x == y) return 1e9;
    //cout << "gogo " << x << " " << y << "\n";
    int np = 31 - __builtin_clz(y - x);
    return min (nmin[x][np], nmin[y-(1<<np)][np]);
}

int Separate(int A, int B)
{
    //cout << "YO\n";
    if (bloc[A] != -1)
        return bbest[bloc[A]][B];
    if (bloc[B] != -1)
        return bbest[bloc[B]][A];
    //return gogo (l[0], r[0]);
    int lloc = 0, rloc = 0;
    int ans = -1;

    while (lloc < floc[A].size() && rloc < floc[B].size())
    {
        ans = max (ans, gogo (floc[A][lloc], floc[B][rloc]));
        if (floc[A][lloc] < floc[B][rloc])
            lloc++;
        else
            rloc++;
    }

    return ans;
}

Compilation message

island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:84:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < floc[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:168:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lloc < floc[A].size() && rloc < floc[B].size())
            ~~~~~^~~~~~~~~~~~~~~~
island.cpp:168:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lloc < floc[A].size() && rloc < floc[B].size())
                                     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 32608 KB Output is correct
2 Correct 261 ms 32612 KB Output is correct
3 Correct 287 ms 32736 KB Output is correct
4 Correct 270 ms 32480 KB Output is correct
5 Correct 264 ms 32612 KB Output is correct
6 Correct 277 ms 32736 KB Output is correct
7 Correct 280 ms 32740 KB Output is correct
8 Correct 263 ms 32740 KB Output is correct
9 Correct 261 ms 32740 KB Output is correct
10 Correct 278 ms 32740 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 216 ms 30564 KB Output is correct
4 Correct 209 ms 33764 KB Output is correct
5 Correct 233 ms 39268 KB Output is correct
6 Correct 240 ms 49252 KB Output is correct
7 Correct 272 ms 68836 KB Output is correct
8 Correct 1871 ms 29540 KB Output is correct
9 Correct 1124 ms 29924 KB Output is correct
10 Correct 773 ms 29792 KB Output is correct
11 Correct 606 ms 29792 KB Output is correct
12 Correct 787 ms 29796 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7424 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 259 ms 32608 KB Output is correct
4 Correct 261 ms 32612 KB Output is correct
5 Correct 287 ms 32736 KB Output is correct
6 Correct 270 ms 32480 KB Output is correct
7 Correct 264 ms 32612 KB Output is correct
8 Correct 277 ms 32736 KB Output is correct
9 Correct 280 ms 32740 KB Output is correct
10 Correct 263 ms 32740 KB Output is correct
11 Correct 261 ms 32740 KB Output is correct
12 Correct 278 ms 32740 KB Output is correct
13 Correct 216 ms 30564 KB Output is correct
14 Correct 209 ms 33764 KB Output is correct
15 Correct 233 ms 39268 KB Output is correct
16 Correct 240 ms 49252 KB Output is correct
17 Correct 272 ms 68836 KB Output is correct
18 Correct 1871 ms 29540 KB Output is correct
19 Correct 1124 ms 29924 KB Output is correct
20 Correct 773 ms 29792 KB Output is correct
21 Correct 606 ms 29792 KB Output is correct
22 Correct 787 ms 29796 KB Output is correct
23 Correct 528 ms 29920 KB Output is correct
24 Correct 399 ms 29924 KB Output is correct
25 Correct 292 ms 29924 KB Output is correct
26 Correct 257 ms 29924 KB Output is correct
27 Correct 286 ms 30048 KB Output is correct
28 Correct 229 ms 30436 KB Output is correct
29 Correct 224 ms 30948 KB Output is correct
30 Correct 283 ms 31972 KB Output is correct
31 Correct 238 ms 32480 KB Output is correct
32 Correct 265 ms 32740 KB Output is correct