oj.uz

Submission #148219

# Submission time Handle Problem Language Result Execution time Memory
148219 2019-08-31T17:51:43 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 78920 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];
vector<int>E[101000], L[101000], FF[101000], ZZ[101000], Fre;
int DD[350][101000], TH = 300, 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;
	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();
	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);
			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]);
		}
	}
	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];

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;
	}


	priority_queue<pii>PQ;
	for (int i=0;i<cnt;i++) {
		int a = ReNum[T[i]];
		D[a] = 1e9;
		vis[a] = 0;
	}
	for (auto &x : FF[A]) {
		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 (int j = 0; j < G[x].size(); j++) {
			int d = max(D[x], GL[x][j]), t = G[x][j];
			if (D[t] > d) {
				D[t] = d;
				PQ.push({ -d, t });
			}
		}
	}
	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:32: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:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (FF[i].size() >= TH) {
       ~~~~~~~~~~~~~^~~~~
island.cpp:79: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:145: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:146: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:189:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < G[x].size(); j++) {
                   ~~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 50364 KB Output is correct
2 Correct 585 ms 50356 KB Output is correct
3 Correct 590 ms 50356 KB Output is correct
4 Correct 524 ms 50368 KB Output is correct
5 Correct 527 ms 50360 KB Output is correct
6 Correct 540 ms 50364 KB Output is correct
7 Correct 661 ms 50356 KB Output is correct
8 Correct 534 ms 50360 KB Output is correct
9 Correct 534 ms 50356 KB Output is correct
10 Correct 529 ms 50356 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14720 KB Output is correct
2 Correct 15 ms 14720 KB Output is correct
3 Correct 431 ms 47484 KB Output is correct
4 Correct 968 ms 50272 KB Output is correct
5 Correct 1637 ms 55952 KB Output is correct
6 Correct 3186 ms 65968 KB Output is correct
7 Execution timed out 5114 ms 78920 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14720 KB Output is correct
2 Correct 15 ms 14720 KB Output is correct
3 Correct 619 ms 50364 KB Output is correct
4 Correct 585 ms 50356 KB Output is correct
5 Correct 590 ms 50356 KB Output is correct
6 Correct 524 ms 50368 KB Output is correct
7 Correct 527 ms 50360 KB Output is correct
8 Correct 540 ms 50364 KB Output is correct
9 Correct 661 ms 50356 KB Output is correct
10 Correct 534 ms 50360 KB Output is correct
11 Correct 534 ms 50356 KB Output is correct
12 Correct 529 ms 50356 KB Output is correct
13 Correct 431 ms 47484 KB Output is correct
14 Correct 968 ms 50272 KB Output is correct
15 Correct 1637 ms 55952 KB Output is correct
16 Correct 3186 ms 65968 KB Output is correct
17 Execution timed out 5114 ms 78920 KB Time limit exceeded
18 Halted 0 ms 0 KB -