oj.uz

Submission #148251

# Submission time Handle Problem Language Result Execution time Memory
148251 2019-08-31T18:30:02 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 47716 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[900][100010], TH = 112, 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 602 ms 46048 KB Output is correct
2 Correct 553 ms 46052 KB Output is correct
3 Correct 469 ms 46056 KB Output is correct
4 Correct 466 ms 46048 KB Output is correct
5 Correct 502 ms 46052 KB Output is correct
6 Correct 656 ms 46052 KB Output is correct
7 Correct 603 ms 46052 KB Output is correct
8 Correct 553 ms 45984 KB Output is correct
9 Correct 535 ms 46004 KB Output is correct
10 Correct 596 ms 46056 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9984 KB Output is correct
2 Correct 14 ms 10008 KB Output is correct
3 Correct 322 ms 43748 KB Output is correct
4 Correct 429 ms 43876 KB Output is correct
5 Correct 494 ms 43748 KB Output is correct
6 Correct 519 ms 44000 KB Output is correct
7 Correct 755 ms 44256 KB Output is correct
8 Correct 1325 ms 45152 KB Output is correct
9 Correct 2416 ms 47716 KB Output is correct
10 Execution timed out 5102 ms 44900 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9984 KB Output is correct
2 Correct 14 ms 10008 KB Output is correct
3 Correct 602 ms 46048 KB Output is correct
4 Correct 553 ms 46052 KB Output is correct
5 Correct 469 ms 46056 KB Output is correct
6 Correct 466 ms 46048 KB Output is correct
7 Correct 502 ms 46052 KB Output is correct
8 Correct 656 ms 46052 KB Output is correct
9 Correct 603 ms 46052 KB Output is correct
10 Correct 553 ms 45984 KB Output is correct
11 Correct 535 ms 46004 KB Output is correct
12 Correct 596 ms 46056 KB Output is correct
13 Correct 322 ms 43748 KB Output is correct
14 Correct 429 ms 43876 KB Output is correct
15 Correct 494 ms 43748 KB Output is correct
16 Correct 519 ms 44000 KB Output is correct
17 Correct 755 ms 44256 KB Output is correct
18 Correct 1325 ms 45152 KB Output is correct
19 Correct 2416 ms 47716 KB Output is correct
20 Execution timed out 5102 ms 44900 KB Time limit exceeded
21 Halted 0 ms 0 KB -