oj.uz

Submission #150667

# Submission time Handle Problem Language Result Execution time Memory
150667 2019-09-01T08:48:05 Z 맞WATLE(#3593, arnold518, ksmzzang2003, songc) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 275 ms 29668 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 29668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -