#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define pii pair<int,int>
#define N_ 101000
vector<int>G[N_], E[N_], L[N_];
int n, m, UF[N_][2], MM[N_];
int Find(int a, int pv) {
if (UF[a][pv] == a)return a;
return UF[a][pv] = Find(UF[a][pv], pv);
}
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);
}
int D[101000][20], Num[101000];
void DFS(int a, int pp, int cur) {
Num[a] = cur;
for (int i = 0; i < E[a].size(); i++) {
int x = E[a][i];
if (x == pp)continue;
D[cur][0] = L[a][i];
DFS(x, a, cur + 1);
}
}
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 = 0; i < n; i++) {
UF[i][0] = i;
UF[i][1] = i;
}
for (i = 0; i < m; i++) {
int a = Find(A[i], 0), b = Find(B[i], 0);
if (a != b) {
int a2 = Find(A[i], 1), b2 = Find(B[i], 1);
Add_Edge(a2, b, i+1);
UF[b][0] = a;
UF[a2][1] = b2;
}
}
DFS(0, -1, 1);
for (i = 0; i < n; i++) {
G[F[i]].push_back(Num[i]);
}
for (i = 0; i < K; i++) {
sort(G[i].begin(), G[i].end());
}
for (i = 0; i < 16; i++) {
for (j = 1; j < n; j++) {
if ((j + (1 << i)) >= n)D[j][i] = 1e9;
else D[j][i+1] = max(D[j][i], D[j + (1 << i)][i]);
}
}
for (i = 1; i <= n; i++) {
MM[i] = MM[i - 1];
if ((1 << (MM[i] + 1)) <= i)MM[i]++;
}
}
int LMQ(int b, int e) {
int t = MM[e - b];
return max(D[b][t], D[e - (1 << t)][t]);
}
map<pii, int>Map;
int Separate(int A, int B) {
if (G[A].size() > G[B].size())swap(A, B);
if (Map.count({ min(A,B),max(A,B) }))return Map[{ min(A, B), max(A, B) }];
int Mn = 1e9;
for (auto &t : G[A]) {
int pv = lower_bound(G[B].begin(), G[B].end(), t) - G[B].begin();
if (pv < G[B].size()) {
Mn = min(Mn, LMQ(t, G[B][pv]));
}
if (pv) {
Mn = min(Mn, LMQ(G[B][pv - 1], t));
}
}
return Map[{ min(A, B), max(A, B) }] = m - Mn + 1;
}
Compilation message
island.cpp: In function 'void DFS(int, int, int)':
island.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E[a].size(); i++) {
~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:82:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pv < G[B].size()) {
~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
329 ms |
36548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
7416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
