Submission #150090

#	Time	Username	Problem	Language	Result	Execution time	Memory
150090		USA1 (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	31 / 100	5099 ms	32740 KiB

island

#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];*/
    vector <int> l = floc[A], r = floc[B];
    //return gogo (l[0], r[0]);
    int lloc = 0, rloc = 0;
    int ans = -1;

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

    return ans;
}

Compilation message (stderr)

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:169:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lloc < l.size() && rloc < r.size())
            ~~~~~^~~~~~~~~~
island.cpp:169:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lloc < l.size() && rloc < r.size())
                               ~~~~~^~~~~~~~~~

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