/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include "island.h"
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 1e5 + 10, M = 3e5 + 10, S = 150, BIG = N / S + 5;
int n, m;
int par[N], sz[N];
vector<int> in_comp[N], at_islands[N];
vector<pii> roots[N];
bool have[N];
int big_finch_id[N], big_precomp[BIG][N];
vector<int> big_finches;
bool is_big_finch[N], big_finches_done[N][BIG];
int get_root(int u);
void merge(int u, int v, int id, vector<int> &f);
void Init(int k, std::vector<int> f, std::vector<int> eu, std::vector<int> ev) {
n = f.size(); m = eu.size();
for (int i = 0; i < n; ++i) {
par[i] = i;
sz[i] = 1;
in_comp[i] = {i};
roots[i].pb({m, i});
at_islands[f[i]].pb(i);
}
for (int i = 0; i < k; ++i) {
if (at_islands[i].size() >= S) {
big_finch_id[i] = big_finches.size();
big_finches.pb(i);
is_big_finch[i] = true;
for (auto &u : at_islands[i]) {
big_finches_done[f[u]][big_finch_id[i]] = true;
big_precomp[big_finch_id[i]][f[u]] = m;
}
}
}
for (int i = m - 1; i >= 0; --i) {
merge(eu[i], ev[i], i, f);
}
}
int Separate(int A, int B) {
if (at_islands[A].size() < at_islands[B].size()) {
swap(A, B);
}
if (is_big_finch[A]) {
return big_precomp[big_finch_id[A]][B] + 1;
} else {
int lo = 1, hi = m - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
bool meet = false;
vector<int> roots_a;
for (auto &u : at_islands[A]) {
auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
roots_a.pb(it->second);
have[it->second] = true;
}
for (auto &u : at_islands[B]) {
auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
if (have[it->second]) {
meet = true;
break;
}
}
for (auto &r : roots_a) {
have[r] = false;
}
if (meet) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return hi + 1;
}
return 0;
}
int get_root(int u) {
if (u != par[u]) {
par[u] = get_root(par[u]);
}
return par[u];
}
void merge(int u, int v, int id, vector<int> &f) {
u = get_root(u);
v = get_root(v);
if (u == v) {
return;
} else if (sz[u] < sz[v]) {
swap(u, v);
}
for (auto &b : big_finches) {
int add_to = -1, bid = big_finch_id[b];
if (big_finches_done[u][bid] xor big_finches_done[v][bid]) {
add_to = (big_finches_done[u][bid] ? v : u);
big_finches_done[add_to][bid] = true;
for (auto &w : in_comp[add_to]) {
big_precomp[bid][f[w]] = max(big_precomp[bid][f[w]], id);
}
}
}
par[v] = u;
for (auto &w : in_comp[v]) {
in_comp[u].pb(w);
roots[w].pb({id, u});
}
in_comp[v].clear();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2455 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 3 |
Runtime error |
2369 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7416 KB |
Output is correct |
| 3 |
Runtime error |
2455 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
