oj.uz

Submission #150644

# Submission time Handle Problem Language Result Execution time Memory
150644 2019-09-01T08:46:04 Z 잉여로운 고3(#3749, imyujin, sebinkim) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 280 ms 26468 KB 
#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=m-1; i>=0; 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

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
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 26340 KB Output is correct
2 Correct 272 ms 26468 KB Output is correct
3 Correct 277 ms 26468 KB Output is correct
4 Correct 272 ms 26468 KB Output is correct
5 Correct 272 ms 26336 KB Output is correct
6 Correct 270 ms 26464 KB Output is correct
7 Correct 255 ms 26464 KB Output is correct
8 Correct 270 ms 26468 KB Output is correct
9 Correct 280 ms 26464 KB Output is correct
10 Correct 262 ms 26340 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2944 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 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -