#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define pii pair<int,int>
#define SZ 262144
int Col[101000], n, m, UF[101000], par[101000][20], Mx[101000][20], Dep[101000], Num[101000], Ed[101000], cnt, D[101000], vis[101000], Fnum[101000];
vector<int>E[101000], L[101000], FF[101000], ZZ[101000], Fre;
int DD[350][101000], TH = 300, ReNum[101000];
int Find(int a) {
if (a == UF[a])return a;
return UF[a] = Find(UF[a]);
}
void Add_Edge(int a, int b, int c) {
E[a].push_back(b);
E[b].push_back(a);
L[a].push_back(c);
L[b].push_back(c);
}
void DFS(int a, int pp) {
Num[a] = ++cnt;
ReNum[cnt] = a;
par[a][0] = pp;
for (int i = 0; i < 18; i++) {
par[a][i + 1] = par[par[a][i]][i];
Mx[a][i + 1] = max(Mx[par[a][i]][i], Mx[a][i]);
}
for (int i = 0; i < E[a].size(); i++) {
int x = E[a][i];
if (x == pp)continue;
Mx[x][0] = L[a][i];
Dep[x] = Dep[a] + 1;
DFS(x, a);
}
Ed[a] = cnt;
}
void Init(int K, std::vector<int> F, std::vector<int> A, std::vector<int> B) {
int i, j;
n = F.size(), m = A.size();
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for (i = 1; i <= n; i++) {
UF[i] = i;
Col[i] = F[i - 1] + 1;
FF[Col[i]].push_back(i);
}
for (i = 0; i < m; i++) {
int a = A[i] + 1, b = B[i] + 1;
if (Find(a) != Find(b)) {
UF[Find(a)] = Find(b);
Add_Edge(a, b, i + 1);
}
}
DFS(1, 0);
for (i = 1; i <= n; i++) {
if (FF[i].size() >= TH) {
Fre.push_back(i);
priority_queue<pii>PQ;
for (j = 1; j <= n; j++) {
D[j] = 1e9;
vis[j] = 0;
}
for (auto &x : FF[i]) {
PQ.push({ 0,x });
D[x] = 0;
}
while (!PQ.empty()) {
pii tp = PQ.top();
PQ.pop();
int x = tp.second;
if (vis[x])continue;
vis[x] = 1;
for (j = 0; j < E[x].size(); j++) {
int d = max(D[x], L[x][j]), t = E[x][j];
if (D[t] > d) {
D[t] = d;
PQ.push({ -d, t });
}
}
}
int cur = Fre.size() - 1;
Fnum[i] = cur;
for (j = 1; j <= n; j++) {
DD[cur][j] = 1e9;
}
for (j = 1; j <= n; j++)DD[cur][Col[j]] = min(DD[cur][Col[j]], D[j]);
}
}
for (i = 1; i <= n; i++)vis[i] = 0;
}
int Up(int a, int d) {
int i = 0;
while (d) {
if (d & 1)a = par[a][i];
d >>= 1; i++;
}
return a;
}
int LCA(int a, int b) {
if (Dep[a] < Dep[b])return LCA(b, a);
int d = Dep[a] - Dep[b], i;
a = Up(a, d);
for (i = 17; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
if (a != b)a = par[a][0];
return a;
}
vector<int>G[101000], GL[101000];
int UpMax(int a, int d) {
int r = 0, i = 0;
while (d) {
if (d & 1) {
r = max(r, Mx[a][i]);
a = par[a][i];
}
d >>= 1; i++;
}
return r;
}
void Add(int a, int b) {
G[a].push_back(b);
G[b].push_back(a);
int d = Dep[a] - Dep[b];
int l = UpMax(a, d);
GL[a].push_back(l);
GL[b].push_back(l);
}
int st[10100];
int T[10100], vv[101000];
int Separate(int A, int B) {
A++, B++;
if (FF[A].size() >= TH)return m + 1 - DD[Fnum[A]][B];
if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
int cnt = 0;
for (auto &t : FF[A])T[cnt++] = Num[t];
for (auto &t : FF[B])T[cnt++] = Num[t];
sort(T, T + cnt);
for (int i = 0; i < cnt; i++)vv[T[i]] = 1;
int tc = cnt;
for (int i = 1; i < tc; i++) {
int a = Num[LCA(ReNum[T[i - 1]], ReNum[T[i]])];
if (!vv[a]) {
vv[a] = 1;
T[cnt++] = a;
}
}
sort(T, T + cnt);
for (int i = 0; i < cnt; i++)vv[T[i]] = 0;
int top = 0;
for (auto &t : T) {
int a = ReNum[t];
while (top && (Num[a] < Num[st[top]] || Ed[st[top]] < Num[a])) top--;
if (top) {
Add(a, st[top]);
}
st[++top] = a;
}
priority_queue<pii>PQ;
for (auto &x : T) {
int a = ReNum[x];
D[a] = 1e9;
vis[a] = 0;
}
for (auto &x : FF[A]) {
PQ.push({ 0,x });
D[x] = 0;
}
while (!PQ.empty()) {
pii tp = PQ.top();
PQ.pop();
int x = tp.second;
if (vis[x])continue;
vis[x] = 1;
for (int j = 0; j < G[x].size(); j++) {
int d = max(D[x], GL[x][j]), t = G[x][j];
if (D[t] > d) {
D[t] = d;
PQ.push({ -d, t });
}
}
}
int res = 1e9;
for (auto &x : FF[B]) {
res = min(res, D[x]);
}
for (auto &t : T) {
int a = ReNum[t];
G[a].clear();
GL[a].clear();
}
return m + 1 - res;
}
Compilation message
island.cpp: In function 'void DFS(int, int)':
island.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[a].size(); i++) {
~~^~~~~~~~~~~~~
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (FF[i].size() >= TH) {
~~~~~~~~~~~~~^~~~~
island.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 0; j < E[x].size(); j++) {
~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:145:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (FF[A].size() >= TH)return m + 1 - DD[Fnum[A]][B];
~~~~~~~~~~~~~^~~~~
island.cpp:146:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
~~~~~~~~~~~~~^~~~~
island.cpp:189:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < G[x].size(); j++) {
~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5104 ms |
47972 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
14976 KB |
Output is correct |
| 2 |
Correct |
17 ms |
15104 KB |
Output is correct |
| 3 |
Correct |
407 ms |
47460 KB |
Output is correct |
| 4 |
Correct |
771 ms |
50276 KB |
Output is correct |
| 5 |
Correct |
1697 ms |
56024 KB |
Output is correct |
| 6 |
Correct |
2533 ms |
65936 KB |
Output is correct |
| 7 |
Execution timed out |
5094 ms |
84144 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
18 ms |
14976 KB |
Output is correct |
| 2 |
Correct |
17 ms |
15104 KB |
Output is correct |
| 3 |
Execution timed out |
5104 ms |
47972 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
