This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |