Submission #150667

#	Time	Username	Problem	Language	Result	Execution time	Memory
150667		맞WATLE (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	275 ms	29668 KiB

island

#include <bits/stdc++.h>
#include "island.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, Q;
vector<pii> adj[101010];
int P[22][101010], dep[101010];
int Pa[101010], id[101010];
int Max[22][101010];

int Find(int u){
	if (Pa[u] == u) return u;
	return Pa[u] = Find(Pa[u]);
}

void dfs(int u, int p){
	for (pii v : adj[u]){
		if (v.first == p) continue;
		dep[v.first] = dep[u] + 1;
		P[0][v.first] = u;
		Max[0][v.first] = v.second;
		dfs(v.first, u);
	}
}

int Maxquery(int u, int v){
	if (dep[u] < dep[v]) swap(u, v);
	int ret = 0;
	for (int i=20; i>=0; i--) if (dep[u] - (1<<i) >= dep[v]) ret = max(ret, Max[i][u]), u = P[i][u];
	if (u == v) return ret;
	for (int i=20; i>=0; i--) if (P[i][u] != P[i][v]){
		ret = max(ret, Max[i][u]);
		ret = max(ret, Max[i][v]);
		u = P[i][u], v = P[i][v];
	}
	ret = max(ret, Max[0][u]);
	ret = max(ret, Max[0][v]);
	return ret;
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	N = F.size(), M = S.size();

	for (int i=0; i<N; i++) id[F[i]] = i;
	for (int i=0; i<N; i++) Pa[i] = i;
	for (int i=M-1; i>=0; i--){
		if (Find(S[i]) == Find(E[i])) continue;
		adj[S[i]].push_back(pii(E[i], i));
		adj[E[i]].push_back(pii(S[i], i));
		Pa[Find(S[i])] = Find(E[i]);
	}

	dep[1] = 1;
	dfs(0, -1);
	for (int i=1; i<=20; i++) for (int j=0; j<N; j++){
		P[i][j] = P[i-1][P[i-1][j]];
		Max[i][j] = max(Max[i-1][j], Max[i-1][P[i-1][j]]);
	}
	puts("ang");
}

int Separate(int A, int B){
	return Maxquery(id[A], id[B]);
}

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