oj.uz

Submission #148203

# Submission time Handle Problem Language Result Execution time Memory
148203 2019-08-31T17:17:53 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 85684 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[250][101000], TH = 400, 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;
}

int IT[SZ + SZ];

void Put(int b, int e, int z) {
	b += SZ, e += SZ;
	while (b <= e) {
		IT[b] = z;
		IT[e] = z;
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
}
int GetMax(int b) {
	int r = 0;
	b += SZ;
	while (b) {
		r = max(r, IT[b]);
		b >>= 1;
	}
	return r;
}

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 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];
	vector<int>T;
	for (auto &t : FF[A])T.push_back(Num[t]);
	for (auto &t : FF[B])T.push_back(Num[t]);
	sort(T.begin(), T.end());
	set<int>V;
	for (auto &t : T)V.insert(t);
	for (int i = 1; i < T.size(); i++) {
		V.insert(Num[LCA(ReNum[T[i - 1]], ReNum[T[i]])]);
	}
	T.clear();
	for (auto &t : V)T.push_back(t);
	for (auto &t : T) {
		int a = ReNum[t];
		int z = GetMax(Num[a]);
		if (z) {
			Add(a, ReNum[z]);
		}
		Put(Num[a], Ed[a], Num[a]);
	}


	priority_queue<pii>PQ;
	for (auto &x : T) {
		int a = ReNum[x];
		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 (auto &t : T) {
		int a = ReNum[t];
		Put(Num[a], Ed[a], 0);
		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:161: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:162: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:169:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < T.size(); i++) {
                  ~~^~~~~~~~~~
island.cpp:200: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 648 ms 50872 KB Output is correct
2 Correct 580 ms 50764 KB Output is correct
3 Correct 771 ms 50772 KB Output is correct
4 Correct 567 ms 50748 KB Output is correct
5 Correct 617 ms 50840 KB Output is correct
6 Correct 731 ms 50876 KB Output is correct
7 Correct 572 ms 50840 KB Output is correct
8 Correct 707 ms 50796 KB Output is correct
9 Correct 672 ms 50760 KB Output is correct
10 Correct 574 ms 50868 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14720 KB Output is correct
2 Correct 17 ms 14720 KB Output is correct
3 Correct 443 ms 47360 KB Output is correct
4 Correct 748 ms 50276 KB Output is correct
5 Correct 1383 ms 56036 KB Output is correct
6 Correct 2864 ms 65916 KB Output is correct
7 Correct 4691 ms 85684 KB Output is correct
8 Execution timed out 5096 ms 79348 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14720 KB Output is correct
2 Correct 17 ms 14720 KB Output is correct
3 Correct 648 ms 50872 KB Output is correct
4 Correct 580 ms 50764 KB Output is correct
5 Correct 771 ms 50772 KB Output is correct
6 Correct 567 ms 50748 KB Output is correct
7 Correct 617 ms 50840 KB Output is correct
8 Correct 731 ms 50876 KB Output is correct
9 Correct 572 ms 50840 KB Output is correct
10 Correct 707 ms 50796 KB Output is correct
11 Correct 672 ms 50760 KB Output is correct
12 Correct 574 ms 50868 KB Output is correct
13 Correct 443 ms 47360 KB Output is correct
14 Correct 748 ms 50276 KB Output is correct
15 Correct 1383 ms 56036 KB Output is correct
16 Correct 2864 ms 65916 KB Output is correct
17 Correct 4691 ms 85684 KB Output is correct
18 Execution timed out 5096 ms 79348 KB Time limit exceeded
19 Halted 0 ms 0 KB -