oj.uz

Submission #150107

# Submission time Handle Problem Language Result Execution time Memory
150107 2019-09-01T07:43:34 Z ----MIT합격선----(#3601, maruii, Diuven, andy627) Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 172 ms 7528 KB 
#include "island.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

pii upa[100000];
int rnk[100000], cnt;
int fnd(int x, int t) { return upa[x].second < t ? x : fnd(upa[x].first, t); }
void uni(int x, int y, int t) {
	x = fnd(x, t), y = fnd(y, t);
	if (x == y) return;
	if (rnk[x] < rnk[y]) swap(x, y);
	upa[y] = {x, t};
	if (rnk[x] == rnk[y]) rnk[x]++;
}

int N, M;
	
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) upa[i] = {i, -1};
	for (int i = M - 1; i >= 0; --i) uni(F[S[i]], F[E[i]], i);
}

int Separate(int A, int B){
	int l = 1, r = M;
	while (l < r) {
		int m = l + r >> 1;
		if (fnd(A, m) != fnd(B, m)) r = m;
		else l = m + 1;
	}
	return l;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 7524 KB Output is correct
2 Correct 163 ms 7396 KB Output is correct
3 Correct 165 ms 7520 KB Output is correct
4 Correct 163 ms 7524 KB Output is correct
5 Correct 167 ms 7528 KB Output is correct
6 Correct 164 ms 7524 KB Output is correct
7 Correct 164 ms 7524 KB Output is correct
8 Correct 171 ms 7524 KB Output is correct
9 Correct 168 ms 7524 KB Output is correct
10 Correct 168 ms 7524 KB Output is correct

Subtask #2
0 / 39.0

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

Subtask #3
0 / 30.0

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