oj.uz

Submission #149220

# Submission time Handle Problem Language Result Execution time Memory
149220 2019-09-01T06:00:12 Z 강력한 한방 필살기(#3595, gs14004, kriii, OnionPringles) Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 2114 ms 72640 KB 
#include "island.h"
#include <bits/stdc++.h>
#define sz(V) ((int)(V).size())
using namespace std;
using pi = pair<int, int>;
const int MAXN = 400005;

struct disj{
	int pa[MAXN];
	void init(int n){
		iota(pa, pa + n + 1, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		if(p < q) swap(p, q);
		pa[q] = p; return 1;
	}
}disj;

int N, piv;
vector<int> gph[MAXN];
vector<int> V[MAXN];
int din[MAXN], dout[MAXN], cst[MAXN];
int elem[20][MAXN];

void dfs(int x){
	for(auto &i : gph[x]){
		din[i] = ++piv;
		elem[0][din[i]] = cst[x];
		dfs(i);
		dout[i] = ++piv;
		elem[0][dout[i]] = cst[x];
	}
}

bool cmp(int x, int y){ return din[x] < din[y]; }

int lg[MAXN];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	for(int i=1; i<MAXN; i++){
		lg[i] = lg[i-1];
		while((2 << lg[i]) <= i) lg[i]++;
	}
	N = sz(F);
	disj.init(2 * N);
	int cnt = N;
	memset(cst, 0x3f, sizeof(cst));
	for(int i=(int)S.size()-1; i>=0; i--){
		int l = disj.find(S[i]);
		int r = disj.find(E[i]);
		if(disj.find(l) != disj.find(r)){
			disj.uni(l, cnt);
			disj.uni(r, cnt);
			cst[cnt] = i + 1;
			gph[cnt].push_back(l);
			gph[cnt].push_back(r);
			cnt++;
		}
	}
	memset(elem, 0x3f, sizeof(elem));
	dfs(cnt - 1);
	for(int i=0; i<N; i++){
		V[F[i]].push_back(i);
	}
	for(int i=0; i<K; i++) sort(V[i].begin(), V[i].end(), cmp);
	for(int i=1; i<20; i++){
		for(int j=1; j<=piv; j++){
			elem[i][j] = elem[i-1][j];
			if(j >= (1 << (i-1))) elem[i][j] = min(elem[i][j], elem[i-1][j - (1<<(i-1))]);
		}
	}
}

int QUERY(int x, int y){
	int L = lg[y - x + 1];
	return min(elem[L][y], elem[L][x + (1<<L) - 1]);
}

map<pi, int> mp;

int Separate(int A, int B){
	if(sz(V[A]) > sz(V[B])) swap(A, B);
	if(mp.find(pi(A, B)) != mp.end()) return mp[pi(A, B)];
	int ret = 0;
	for(auto &i : V[A]){
		auto itr = upper_bound(V[B].begin(), V[B].end(), i, cmp);
		if(itr != V[B].begin()){
			ret = max(ret, QUERY(dout[*prev(itr)], din[i]));
		}
		if(itr != V[B].end()){
			ret = max(ret, QUERY(din[i] + 1, din[*itr]));
		}
	}
	mp[pi(A, B)] = mp[pi(B, A)] = ret;
	return ret;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 72636 KB Output is correct
2 Correct 356 ms 72636 KB Output is correct
3 Correct 415 ms 72632 KB Output is correct
4 Correct 423 ms 72636 KB Output is correct
5 Correct 413 ms 72636 KB Output is correct
6 Correct 362 ms 72636 KB Output is correct
7 Correct 372 ms 72640 KB Output is correct
8 Correct 378 ms 72636 KB Output is correct
9 Correct 389 ms 72636 KB Output is correct
10 Correct 367 ms 72632 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 53632 KB Output is correct
2 Correct 49 ms 53632 KB Output is correct
3 Correct 283 ms 66272 KB Output is correct
4 Correct 338 ms 66364 KB Output is correct
5 Correct 468 ms 66144 KB Output is correct
6 Correct 603 ms 66148 KB Output is correct
7 Correct 1306 ms 66152 KB Output is correct
8 Correct 2114 ms 66616 KB Output is correct
9 Correct 1540 ms 69172 KB Output is correct
10 Correct 1302 ms 69736 KB Output is correct
11 Correct 1311 ms 69756 KB Output is correct
12 Correct 1105 ms 69812 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 53632 KB Output is correct
2 Correct 49 ms 53632 KB Output is correct
3 Correct 443 ms 72636 KB Output is correct
4 Correct 356 ms 72636 KB Output is correct
5 Correct 415 ms 72632 KB Output is correct
6 Correct 423 ms 72636 KB Output is correct
7 Correct 413 ms 72636 KB Output is correct
8 Correct 362 ms 72636 KB Output is correct
9 Correct 372 ms 72640 KB Output is correct
10 Correct 378 ms 72636 KB Output is correct
11 Correct 389 ms 72636 KB Output is correct
12 Correct 367 ms 72632 KB Output is correct
13 Correct 283 ms 66272 KB Output is correct
14 Correct 338 ms 66364 KB Output is correct
15 Correct 468 ms 66144 KB Output is correct
16 Correct 603 ms 66148 KB Output is correct
17 Correct 1306 ms 66152 KB Output is correct
18 Correct 2114 ms 66616 KB Output is correct
19 Correct 1540 ms 69172 KB Output is correct
20 Correct 1302 ms 69736 KB Output is correct
21 Correct 1311 ms 69756 KB Output is correct
22 Correct 1105 ms 69812 KB Output is correct
23 Correct 1161 ms 69948 KB Output is correct
24 Correct 628 ms 70204 KB Output is correct
25 Correct 673 ms 70208 KB Output is correct
26 Correct 455 ms 70332 KB Output is correct
27 Correct 504 ms 70348 KB Output is correct
28 Correct 430 ms 70636 KB Output is correct
29 Correct 417 ms 71092 KB Output is correct
30 Correct 428 ms 71988 KB Output is correct
31 Correct 405 ms 72380 KB Output is correct
32 Correct 417 ms 72636 KB Output is correct