Submission #151324

#	Time	Username	Problem	Language	Result	Execution time	Memory
151324		ainta	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	4861 ms	56268 KiB

island

#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], Fre, Ch[101000];
int DD[1260][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 <= K; 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[1010], GL[1010];
int NN[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;
}
 
int Dist(int a, int b) {
	int d = Dep[a] - Dep[b];
	int l = UpMax(a, d);
	return l;
}
 
void Add(int a, int b, int l) {
	G[a].push_back(b);
	G[b].push_back(a);
	GL[a].push_back(l);
	GL[b].push_back(l);
}
 
int st[10100];
 
int T[10100], vv[101000];
 
void Do3(int a, int pp) {
	for (int i = 0; i < G[a].size(); i++) {
		int x = G[a][i], l = GL[a][i];
		if (x == pp)continue;
		Do3(x, a);
		D[a] = min(D[a], max(D[x], l));
	}
}
void Do4(int a, int pp) {
	for (int i = 0; i < G[a].size(); i++) {
		int x = G[a][i], l = GL[a][i];
		if (x == pp)continue;
		D[x] = min(D[x], max(D[a], l));
		Do4(x, a);
	}
}
 
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;
		NN[ReNum[T[i]]] = i + 1;
	}
	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(NN[a], NN[st[top]], Dist(a,st[top]));
		}
		st[++top] = a;
	}
 
	for (int i = 1; i <= cnt; i++) D[i] = 1e9;
 
 
	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		if (Col[a] == A) D[i + 1] = 0;
	}
 
	Do3(1, 0);
	Do4(1, 0);
 
 
	int res = 1e9;
	for (int i = 0; i < cnt; i++) {
		int a = ReNum[T[i]];
		if (Col[a] == B) {
			res = min(res, D[i + 1]);
		}
	}
 
	for (int i = 1; i <= cnt; i++) {
		G[i].clear();
		GL[i].clear();
	}
	return m + 1 - res;
}

Compilation message (stderr)

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 'void Do3(int, int)':
island.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'void Do4(int, int)':
island.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < G[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:169: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:170:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (FF[B].size() >= TH)return m + 1 - DD[Fnum[B]][A];
      ~~~~~~~~~~~~~^~~~~

• Subtask 1: 31 / 31
• Subtask 2: 39 / 39
• Subtask 3: 30 / 30