Submission #151568

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

island

#include "island.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define pii pair<int,int>
#define N_ 101000

vector<int>G[N_], E[N_], L[N_];
int n, m, UF[N_][2], MM[N_];
int Find(int a, int pv) {
	if (UF[a][pv] == a)return a;
	return UF[a][pv] = Find(UF[a][pv], pv);
}
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);
}
int D[101000][20], Num[101000];
void DFS(int a, int pp, int cur) {
	Num[a] = cur;
	for (int i = 0; i < E[a].size(); i++) {
		int x = E[a][i];
		if (x == pp)continue;
		D[cur][0] = L[a][i];
		DFS(x, a, cur + 1);
	}
}
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 = 0; i < n; i++) {
		UF[i][0] = i;
		UF[i][1] = i;
	}
	for (i = 0; i < m; i++) {
		int a = Find(A[i], 0), b = Find(B[i], 0);
		if (a != b) {
			int a2 = Find(A[i], 1), b2 = Find(B[i], 1);
			Add_Edge(a2, b, i+1);
			UF[b][0] = a;
			UF[a2][1] = b2;
		}
	}
	DFS(Find(0,0), -1, 1);
	for (i = 0; i < n; i++) {
		G[F[i]].push_back(Num[i]);
	}
	for (i = 0; i < K; i++) {
		sort(G[i].begin(), G[i].end());
	}
	for (i = 0; i < 16; i++) {
		for (j = 1; j < n; j++) {
			if ((j + (1 << i)) >= n)D[j][i+1] = 1e9;
			else D[j][i+1] = max(D[j][i], D[j + (1 << i)][i]);
		}
	}
	for (i = 1; i <= n; i++) {
		MM[i] = MM[i - 1];
		if ((1 << (MM[i] + 1)) <= i)MM[i]++;
	}
}

int LMQ(int b, int e) {
	int t = MM[e - b];
	return max(D[b][t], D[e - (1 << t)][t]);
}

map<pii, int>Map;

int Separate(int A, int B) {
	if (G[A].size() > G[B].size())swap(A, B);
	if (Map.count({ min(A,B),max(A,B) }))return Map[{ min(A, B), max(A, B) }];
	int Mn = 1e9;
	for (auto &t : G[A]) {
		int pv = lower_bound(G[B].begin(), G[B].end(), t) - G[B].begin();
		if (pv < G[B].size()) {
			Mn = min(Mn, LMQ(t, G[B][pv]));
		}
		if (pv) {
			Mn = min(Mn, LMQ(G[B][pv - 1], t));
		}
	}
	return Map[{ min(A, B), max(A, B) }] = m - Mn + 1;
}

Compilation message (stderr)

island.cpp: In function 'void DFS(int, int, int)':
island.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E[a].size(); i++) {
                  ~~^~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:82:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pv < G[B].size()) {
       ~~~^~~~~~~~~~~~~

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