Submission #150612

#	Time	Username	Problem	Language	Result	Execution time	Memory
150612		잉여로운 고3 (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	270 ms	26468 KiB

island

#include <bits/stdc++.h>

#include "island.h"

using namespace std;

typedef pair <int, int> pii;

vector <pii> T[101010];
int P[22][101010], K[22][101010];
int X[101010], D[101010], U[101010];
int n, m;

int find(int p) { return p == U[p]? p : U[p] = find(U[p]); }

void dfs(int p, int r)
{
	for(pii &t: T[p]){
		if(t.first != r){
			D[t.first] = D[p] + 1;
			P[0][t.first] = p;
			K[0][t.first] = t.second;
			dfs(t.first, p);
		}
	}
}

void Init(int k, vector <int> F, vector <int> S, vector <int> E)
{
	int i, j;
	
	n = F.size(), m = S.size();
	
	for(i=0; i<n; i++){
		X[F[i]] = i;
		U[i] = i;
	}
	
	for(i=0; i<m; i++){
		if(find(S[i]) != find(E[i])){
			T[S[i]].emplace_back(E[i], i + 1);
			T[E[i]].emplace_back(S[i], i + 1);
			U[find(S[i])] = find(E[i]);
		}
	}
	
	dfs(0, 0);
	
	for(i=1; i<=16; i++){
		for(j=0; j<n; j++){
			P[i][j] = P[i - 1][P[i - 1][j]];
			K[i][j] = min(K[i - 1][j], K[i - 1][P[i - 1][j]]);
		}
	}
}

int Separate(int p, int q)
{
	p = X[p]; q = X[q];
	if(D[p] < D[q]) swap(p, q);
	
	int i, ans;
	
	ans = 1e9;
	
	for(i=0; i<=16; i++){
		if(D[p] - D[q] & 1 << i){
			ans = min(ans, K[i][p]);
			p = P[i][p];
		}
	}
	
	if(p == q) return ans;
	
	for(i=16; i>=0; i--){
		if(P[i][p] != P[i][q]){
			ans = min(ans, min(K[i][p], K[i][q]));
			p = P[i][p]; q = P[i][q];
		}
	}
	
	return min(ans, min(K[0][p], K[0][q]));
}

Compilation message (stderr)

island.cpp: In function 'int Separate(int, int)':
island.cpp:67:11: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   if(D[p] - D[q] & 1 << i){
      ~~~~~^~~~~~

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