Submission #151636

#	Time	Username	Problem	Language	Result	Execution time	Memory
151636		kuroni	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	3380 ms	32844 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 100005;

int m, dsu[N];
map<pair<int, int>, int> ma;
vector<int> col[N];
vector<pair<int, int>> ele[N], com[N];

int trace(int u)
{
    return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
}

void connect(int u, int v, int ind)
{
    if ((u = trace(u)) == (v = trace(v)))
        return;
    if (dsu[u] > dsu[v])
        swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;
    for (pair<int, int> &tmp : ele[v])
    {
        int cur = tmp.fi;
        ele[u].push_back({cur, ind});
        com[cur].push_back({u, ind});
    }
}

void Init(int k, std::vector<int> f, std::vector<int> s, std::vector<int> e)
{
    int n = f.size();
    for (int i = 0; i < n; i++)
    {
        dsu[i] = -1;
        col[f[i]].push_back(i);
        ele[i].push_back({i, -1});
        com[i].push_back({i, -1});
    }
    m = s.size();
    for (int i = 0; i < m; i++)
    {
        int u = s[m - 1 - i], v = e[m - 1 - i];
        connect(u, v, i);
    }
    for (int i = 0; i < n; i++)
    {
        for (pair<int, int> &v : ele[i])
            v.fi = f[v.fi];
        sort(ele[i].begin(), ele[i].end());
    }
}

int Separate(int u, int v)
{
    if (col[u].size() > col[v].size() || (col[u].size() == col[v].size() && u > v))
        swap(u, v);
    if (ma.count({u, v}) > 0)
        return ma[{u, v}];
    int ans = m + 1;
    for (int &x : col[u])
    {
        int le = 0, ri = com[x].size();
        while (le <= ri)
        {
            int mi = (le + ri) / 2;
            int cur = com[x][mi].fi;
            auto it = lower_bound(ele[cur].begin(), ele[cur].end(), make_pair(v, -1));
            if (it == ele[cur].end() || it->fi != v)
                le = mi + 1;
            else
            {
                ans = min(ans, max(com[x][mi].se, it->se));
                ri = mi - 1;
            }
        }
    }
    return ma[{u, v}] = m - ans;
}

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