oj.uz

Submission #148200

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

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 655 ms 50788 KB Output is correct
2 Correct 708 ms 50872 KB Output is correct
3 Correct 616 ms 50872 KB Output is correct
4 Correct 747 ms 50876 KB Output is correct
5 Correct 691 ms 50876 KB Output is correct
6 Correct 680 ms 50860 KB Output is correct
7 Correct 575 ms 50804 KB Output is correct
8 Correct 732 ms 50900 KB Output is correct
9 Correct 750 ms 50876 KB Output is correct
10 Correct 673 ms 50824 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 31 ms 14720 KB Output is correct
3 Correct 505 ms 47460 KB Output is correct
4 Correct 817 ms 50272 KB Output is correct
5 Correct 1573 ms 56032 KB Output is correct
6 Correct 2680 ms 65920 KB Output is correct
7 Correct 4809 ms 85728 KB Output is correct
8 Execution timed out 5097 ms 79716 KB Time limit exceeded
9 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 31 ms 14720 KB Output is correct
3 Correct 655 ms 50788 KB Output is correct
4 Correct 708 ms 50872 KB Output is correct
5 Correct 616 ms 50872 KB Output is correct
6 Correct 747 ms 50876 KB Output is correct
7 Correct 691 ms 50876 KB Output is correct
8 Correct 680 ms 50860 KB Output is correct
9 Correct 575 ms 50804 KB Output is correct
10 Correct 732 ms 50900 KB Output is correct
11 Correct 750 ms 50876 KB Output is correct
12 Correct 673 ms 50824 KB Output is correct
13 Correct 505 ms 47460 KB Output is correct
14 Correct 817 ms 50272 KB Output is correct
15 Correct 1573 ms 56032 KB Output is correct
16 Correct 2680 ms 65920 KB Output is correct
17 Correct 4809 ms 85728 KB Output is correct
18 Execution timed out 5097 ms 79716 KB Time limit exceeded
19 Halted 0 ms 0 KB -