oj.uz

Submission #148252

# Submission time Handle Problem Language Result Execution time Memory
148252 2019-08-31T18:31:35 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
70 / 100
 5000 ms 52316 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 612 ms 46048 KB Output is correct
2 Correct 617 ms 46048 KB Output is correct
3 Correct 586 ms 46052 KB Output is correct
4 Correct 565 ms 46048 KB Output is correct
5 Correct 585 ms 46048 KB Output is correct
6 Correct 576 ms 46052 KB Output is correct
7 Correct 595 ms 45996 KB Output is correct
8 Correct 554 ms 46048 KB Output is correct
9 Correct 541 ms 46048 KB Output is correct
10 Correct 599 ms 46052 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9984 KB Output is correct
2 Correct 12 ms 10008 KB Output is correct
3 Correct 442 ms 43772 KB Output is correct
4 Correct 421 ms 43876 KB Output is correct
5 Correct 502 ms 43744 KB Output is correct
6 Correct 596 ms 44000 KB Output is correct
7 Correct 697 ms 44260 KB Output is correct
8 Correct 1210 ms 45156 KB Output is correct
9 Correct 2492 ms 47716 KB Output is correct
10 Correct 4176 ms 52304 KB Output is correct
11 Correct 4035 ms 52256 KB Output is correct
12 Correct 4045 ms 52316 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9984 KB Output is correct
2 Correct 12 ms 10008 KB Output is correct
3 Correct 612 ms 46048 KB Output is correct
4 Correct 617 ms 46048 KB Output is correct
5 Correct 586 ms 46052 KB Output is correct
6 Correct 565 ms 46048 KB Output is correct
7 Correct 585 ms 46048 KB Output is correct
8 Correct 576 ms 46052 KB Output is correct
9 Correct 595 ms 45996 KB Output is correct
10 Correct 554 ms 46048 KB Output is correct
11 Correct 541 ms 46048 KB Output is correct
12 Correct 599 ms 46052 KB Output is correct
13 Correct 442 ms 43772 KB Output is correct
14 Correct 421 ms 43876 KB Output is correct
15 Correct 502 ms 43744 KB Output is correct
16 Correct 596 ms 44000 KB Output is correct
17 Correct 697 ms 44260 KB Output is correct
18 Correct 1210 ms 45156 KB Output is correct
19 Correct 2492 ms 47716 KB Output is correct
20 Correct 4176 ms 52304 KB Output is correct
21 Correct 4035 ms 52256 KB Output is correct
22 Correct 4045 ms 52316 KB Output is correct
23 Correct 4824 ms 50672 KB Output is correct
24 Execution timed out 5104 ms 43492 KB Time limit exceeded
25 Halted 0 ms 0 KB -