oj.uz

Submission #148240

# Submission time Handle Problem Language Result Execution time Memory
148240 2019-08-31T18:19:13 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
70 / 100
 5000 ms 60548 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[1667][100010], TH = 60, 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[101000], GL[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;
}

void Add(int a, int b) {
	G[a].push_back(b);
	G[b].push_back(a);
	int d = Dep[a] - Dep[b];
	int l = UpMax(a, d);
	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;
	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(a, st[top]);
		}
		st[++top] = a;
	}

	for (int i=0;i<cnt;i++) {
		int a = ReNum[T[i]];
		D[a] = 1e9;
	}

	for (auto &x : FF[A])D[x] = 0;

	Do3(ReNum[T[0]], 0);
	Do4(ReNum[T[0]], 0);


	int res = 1e9;
	for (auto &x : FF[B]) {
		res = min(res, D[x]);
	}

	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		G[a].clear();
		GL[a].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:146: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:154: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:164: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:165: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 741 ms 53052 KB Output is correct
2 Correct 588 ms 53076 KB Output is correct
3 Correct 651 ms 53112 KB Output is correct
4 Correct 550 ms 53088 KB Output is correct
5 Correct 551 ms 53052 KB Output is correct
6 Correct 628 ms 53052 KB Output is correct
7 Correct 660 ms 53052 KB Output is correct
8 Correct 562 ms 53080 KB Output is correct
9 Correct 604 ms 53044 KB Output is correct
10 Correct 512 ms 53052 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14720 KB Output is correct
2 Correct 16 ms 14720 KB Output is correct
3 Correct 352 ms 48412 KB Output is correct
4 Correct 415 ms 48612 KB Output is correct
5 Correct 501 ms 48480 KB Output is correct
6 Correct 623 ms 48740 KB Output is correct
7 Correct 739 ms 48992 KB Output is correct
8 Correct 1391 ms 49896 KB Output is correct
9 Correct 2664 ms 52476 KB Output is correct
10 Correct 4176 ms 57224 KB Output is correct
11 Correct 4197 ms 57188 KB Output is correct
12 Correct 4330 ms 57248 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14720 KB Output is correct
2 Correct 16 ms 14720 KB Output is correct
3 Correct 741 ms 53052 KB Output is correct
4 Correct 588 ms 53076 KB Output is correct
5 Correct 651 ms 53112 KB Output is correct
6 Correct 550 ms 53088 KB Output is correct
7 Correct 551 ms 53052 KB Output is correct
8 Correct 628 ms 53052 KB Output is correct
9 Correct 660 ms 53052 KB Output is correct
10 Correct 562 ms 53080 KB Output is correct
11 Correct 604 ms 53044 KB Output is correct
12 Correct 512 ms 53052 KB Output is correct
13 Correct 352 ms 48412 KB Output is correct
14 Correct 415 ms 48612 KB Output is correct
15 Correct 501 ms 48480 KB Output is correct
16 Correct 623 ms 48740 KB Output is correct
17 Correct 739 ms 48992 KB Output is correct
18 Correct 1391 ms 49896 KB Output is correct
19 Correct 2664 ms 52476 KB Output is correct
20 Correct 4176 ms 57224 KB Output is correct
21 Correct 4197 ms 57188 KB Output is correct
22 Correct 4330 ms 57248 KB Output is correct
23 Correct 4960 ms 60548 KB Output is correct
24 Execution timed out 5098 ms 52796 KB Time limit exceeded
25 Halted 0 ms 0 KB -