oj.uz

답안 #148233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
148233 2019-08-31T18:08:20 Z 조팍시\n123(#3740, tlwpdus, ainta, cki86201) 갈라파고스 여행 (FXCUP4_island) C++17
31 / 100
 719 ms 55512 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], ZZ[101000], Fre, Ch[101000];
int DD[1251][100010], TH = 80, 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 <= n; j++)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: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 'int Separate(int, int)':
island.cpp:146: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:147: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:190: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

# 결과 실행 시간 메모리 Grader output
1 Correct 718 ms 55480 KB Output is correct
2 Correct 617 ms 55424 KB Output is correct
3 Correct 509 ms 55500 KB Output is correct
4 Correct 646 ms 55512 KB Output is correct
5 Correct 677 ms 55440 KB Output is correct
6 Correct 647 ms 55504 KB Output is correct
7 Correct 540 ms 55480 KB Output is correct
8 Correct 614 ms 55508 KB Output is correct
9 Correct 719 ms 55488 KB Output is correct
10 Correct 692 ms 55504 KB Output is correct

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 17024 KB Output is correct
2 Correct 20 ms 17080 KB Output is correct
3 Incorrect 362 ms 50784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 17024 KB Output is correct
2 Correct 20 ms 17080 KB Output is correct
3 Correct 718 ms 55480 KB Output is correct
4 Correct 617 ms 55424 KB Output is correct
5 Correct 509 ms 55500 KB Output is correct
6 Correct 646 ms 55512 KB Output is correct
7 Correct 677 ms 55440 KB Output is correct
8 Correct 647 ms 55504 KB Output is correct
9 Correct 540 ms 55480 KB Output is correct
10 Correct 614 ms 55508 KB Output is correct
11 Correct 719 ms 55488 KB Output is correct
12 Correct 692 ms 55504 KB Output is correct
13 Incorrect 362 ms 50784 KB Output isn't correct
14 Halted 0 ms 0 KB -