oj.uz

Submission #148202

# Submission time Handle Problem Language Result Execution time Memory
148202 2019-08-31T17:16:46 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 82912 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[510][101000], TH = 200, 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 602 ms 50876 KB Output is correct
2 Correct 668 ms 50900 KB Output is correct
3 Correct 634 ms 50864 KB Output is correct
4 Correct 713 ms 50808 KB Output is correct
5 Correct 617 ms 50748 KB Output is correct
6 Correct 585 ms 50780 KB Output is correct
7 Correct 572 ms 50872 KB Output is correct
8 Correct 769 ms 50876 KB Output is correct
9 Correct 564 ms 50780 KB Output is correct
10 Correct 580 ms 50820 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14720 KB Output is correct
2 Correct 17 ms 14848 KB Output is correct
3 Correct 466 ms 47484 KB Output is correct
4 Correct 765 ms 50272 KB Output is correct
5 Correct 1437 ms 55952 KB Output is correct
6 Correct 2959 ms 65884 KB Output is correct
7 Execution timed out 5107 ms 82912 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14720 KB Output is correct
2 Correct 17 ms 14848 KB Output is correct
3 Correct 602 ms 50876 KB Output is correct
4 Correct 668 ms 50900 KB Output is correct
5 Correct 634 ms 50864 KB Output is correct
6 Correct 713 ms 50808 KB Output is correct
7 Correct 617 ms 50748 KB Output is correct
8 Correct 585 ms 50780 KB Output is correct
9 Correct 572 ms 50872 KB Output is correct
10 Correct 769 ms 50876 KB Output is correct
11 Correct 564 ms 50780 KB Output is correct
12 Correct 580 ms 50820 KB Output is correct
13 Correct 466 ms 47484 KB Output is correct
14 Correct 765 ms 50272 KB Output is correct
15 Correct 1437 ms 55952 KB Output is correct
16 Correct 2959 ms 65884 KB Output is correct
17 Execution timed out 5107 ms 82912 KB Time limit exceeded
18 Halted 0 ms 0 KB -