oj.uz

Submission #151324

# Submission time Handle Problem Language Result Execution time Memory
151324 2019-09-02T13:08:45 Z ainta Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 4861 ms 56268 KB 
#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], pL[101000], P[101000];
vector<int>E[101000], L[101000], FF[101000], Fre, Ch[101000];
int DD[1260][100010], TH = 80, 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;
	P[a] = 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];
		pL[x] = L[a][i];
		Dep[x] = Dep[a] + 1;
		Ch[a].push_back(x);
		DFS(x, a);
	}
	Ed[a] = cnt;
}
 
void Do1(int a) {
	int i;
	for (i = n; i > 1; i--) {
		int a = ReNum[i];
		D[P[a]] = min(D[P[a]], max(D[a], pL[a]));
	}
}
void Do2(int a) {
	int i;
	for (i = 2; i <= n; i++) {
		int a = ReNum[i];
		D[a] = min(D[a], max(D[P[a]], pL[a]));
	}
}
 
 
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);
			for (j = 1; j <= n; j++) {
				D[j] = 1e9;
				vis[j] = 0;
			}
			for (auto &x : FF[i]) {
				D[x] = 0;
			}
			Do1(1);
			Do2(1);
			int cur = Fre.size() - 1;
			Fnum[i] = cur;
			for (j = 1; j <= K; 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[1010], GL[1010];
int NN[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;
}
 
int Dist(int a, int b) {
	int d = Dep[a] - Dep[b];
	int l = UpMax(a, d);
	return l;
}
 
void Add(int a, int b, int l) {
	G[a].push_back(b);
	G[b].push_back(a);
	GL[a].push_back(l);
	GL[b].push_back(l);
}
 
int st[10100];
 
int T[10100], vv[101000];
 
void Do3(int a, int pp) {
	for (int i = 0; i < G[a].size(); i++) {
		int x = G[a][i], l = GL[a][i];
		if (x == pp)continue;
		Do3(x, a);
		D[a] = min(D[a], max(D[x], l));
	}
}
void Do4(int a, int pp) {
	for (int i = 0; i < G[a].size(); i++) {
		int x = G[a][i], l = GL[a][i];
		if (x == pp)continue;
		D[x] = min(D[x], max(D[a], l));
		Do4(x, a);
	}
}
 
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;
		NN[ReNum[T[i]]] = i + 1;
	}
	int top = 0;
	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		while (top && (Num[a] < Num[st[top]] || Ed[st[top]] < Num[a])) top--;
		if (top) {
			Add(NN[a], NN[st[top]], Dist(a,st[top]));
		}
		st[++top] = a;
	}
 
	for (int i = 1; i <= cnt; i++) D[i] = 1e9;
 
 
	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		if (Col[a] == A) D[i + 1] = 0;
	}
 
	Do3(1, 0);
	Do4(1, 0);
 
 
	int res = 1e9;
	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		if (Col[a] == B) {
			res = min(res, D[i + 1]);
		}
	}
 
	for (int i = 1; i <= cnt; i++) {
		G[i].clear();
		GL[i].clear();
	}
	return m + 1 - res;
}

Compilation message

island.cpp: In function 'void DFS(int, int)':
island.cpp:33: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:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (FF[i].size() >= TH) {
       ~~~~~~~~~~~~~^~~~~
island.cpp: In function 'void Do3(int, int)':
island.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'void Do4(int, int)':
island.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:169: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:170:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
      ~~~~~~~~~~~~~^~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 50100 KB Output is correct
2 Correct 393 ms 50144 KB Output is correct
3 Correct 423 ms 50172 KB Output is correct
4 Correct 387 ms 50116 KB Output is correct
5 Correct 403 ms 49964 KB Output is correct
6 Correct 393 ms 50016 KB Output is correct
7 Correct 395 ms 50112 KB Output is correct
8 Correct 391 ms 50020 KB Output is correct
9 Correct 420 ms 50084 KB Output is correct
10 Correct 402 ms 50020 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9976 KB Output is correct
3 Correct 300 ms 47600 KB Output is correct
4 Correct 344 ms 47612 KB Output is correct
5 Correct 419 ms 47772 KB Output is correct
6 Correct 525 ms 47840 KB Output is correct
7 Correct 761 ms 48080 KB Output is correct
8 Correct 1326 ms 49060 KB Output is correct
9 Correct 2787 ms 51744 KB Output is correct
10 Correct 4635 ms 56268 KB Output is correct
11 Correct 4647 ms 56192 KB Output is correct
12 Correct 4650 ms 56100 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9976 KB Output is correct
3 Correct 386 ms 50100 KB Output is correct
4 Correct 393 ms 50144 KB Output is correct
5 Correct 423 ms 50172 KB Output is correct
6 Correct 387 ms 50116 KB Output is correct
7 Correct 403 ms 49964 KB Output is correct
8 Correct 393 ms 50016 KB Output is correct
9 Correct 395 ms 50112 KB Output is correct
10 Correct 391 ms 50020 KB Output is correct
11 Correct 420 ms 50084 KB Output is correct
12 Correct 402 ms 50020 KB Output is correct
13 Correct 300 ms 47600 KB Output is correct
14 Correct 344 ms 47612 KB Output is correct
15 Correct 419 ms 47772 KB Output is correct
16 Correct 525 ms 47840 KB Output is correct
17 Correct 761 ms 48080 KB Output is correct
18 Correct 1326 ms 49060 KB Output is correct
19 Correct 2787 ms 51744 KB Output is correct
20 Correct 4635 ms 56268 KB Output is correct
21 Correct 4647 ms 56192 KB Output is correct
22 Correct 4650 ms 56100 KB Output is correct
23 Correct 4861 ms 54780 KB Output is correct
24 Correct 3614 ms 47588 KB Output is correct
25 Correct 2436 ms 47608 KB Output is correct
26 Correct 1539 ms 47720 KB Output is correct
27 Correct 1185 ms 47732 KB Output is correct
28 Correct 623 ms 48008 KB Output is correct
29 Correct 485 ms 48608 KB Output is correct
30 Correct 455 ms 49376 KB Output is correct
31 Correct 409 ms 49840 KB Output is correct
32 Correct 427 ms 50280 KB Output is correct