#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define pii pair<int,int>
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[1010][101000], TH = 1;
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;
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();
for (i = 1; i <= n; i++) {
UF[i] = i;
Col[i] = F[i - 1] + 1;
FF[Col[i]].push_back(i);
}
vector<int>U;
for (i = 0; i < m; i++) {
int a = A[i] + 1, b = B[i] + 1;
U.push_back(i);
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]);
}
}
}
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];
}
Compilation message
island.cpp: In function 'void DFS(int, int)':
island.cpp:29: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:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (FF[i].size() >= TH) {
~~~~~~~~~~~~~^~~~~
island.cpp:76: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:96: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:97: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:98:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5112 ms |
88224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
9984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
9984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
