oj.uz

Submission #762469

# Submission time Handle Problem Language Result Execution time Memory
762469 2023-06-21T12:25:09 Z goodbyehanbyeol Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 4813 ms 50036 KB 
#include "island.h"
#include <bits/stdc++.h>
using namespace std;

const int NS = (int)2e5 + 4;
int lca[NS][24], pr[NS];
int n, m, ncnt, k;
vector<int> gr[NS], way[NS];
int euler[NS], en, tim[NS], dep[NS];
int eback[NS];

int fd(int x){
	return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}

void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int n = F.size(), m = S.size(), k = K;
	for(int i = 0; i < NS; ++i){
		pr[i] = i;
	}

	ncnt = n;
	for(int i = m - 1; i >= 0; --i){
		int x = S[i], y = E[i];
		int px = fd(x), py = fd(y);
		if(px == py){
			continue;
		}

		pr[px] = pr[py] = ncnt;
		lca[px][0] = lca[py][0] = ncnt;
		way[ncnt] = {px, py};
		tim[ncnt] = i;
		++ncnt;
	}

	for(int j = 1; j < 20; ++j){
		for(int i = 0; i < ncnt; ++i){
			lca[i][j] = lca[lca[i][j - 1]][j - 1];
		}
	}

	auto dfs = [&](auto&&self, int x)->void{
		euler[x] = ++en;
		eback[en] = x;
		for(auto&nxt:way[x]){
			dep[nxt] = dep[x] + 1;
			self(self, nxt);
		}
	};
	dfs(dfs, ncnt - 1);

	for(int i = 0; i < n; ++i){
		gr[F[i]].push_back(euler[i]);
	}
	for(int i = 0; i < k; ++i){
		sort(gr[i].begin(), gr[i].end());
	}
}

int gettime(int x, int y){
	// cout << "FIND " << x << ' ' << y << endl;
	if(dep[x] > dep[y]){
		swap(x, y);
	}
	for(int i = 19; i >= 0; --i){
		if(dep[y] - (1 << i) >= dep[x]){
			y = lca[y][i];
		}
	}
	if(x == y) return tim[x];
	for(int i = 19; i >= 0; --i){
		if(lca[x][i] != lca[y][i]){
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	return tim[lca[x][0]];
}

map<pair<int, int>, int> save;

int Separate(int A, int B){
	int a = A, b = B;
	if(a > b){
		swap(a, b);
	}
	auto it = save.find(make_pair(a, b));
	if(it != save.end()){
		return it->second;
	}

	int ans = 0;
	if((int)gr[A].size() > (int)gr[B].size()) swap(A, B);
	for(int i = 0; i < (int)gr[A].size(); ++i){
		int pos = lower_bound(gr[B].begin(), gr[B].end(), gr[A][i]) - gr[B].begin();
		if(pos < (int)gr[B].size()){
			ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
		}
		if(pos){
			--pos;
			ans = max(ans, gettime(eback[gr[A][i]], eback[gr[B][pos]]));
		}
	}

	save[{a, b}] = ans + 1;

	return ans + 1;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 49916 KB Output is correct
2 Correct 202 ms 50016 KB Output is correct
3 Correct 222 ms 50000 KB Output is correct
4 Correct 206 ms 49992 KB Output is correct
5 Correct 193 ms 49968 KB Output is correct
6 Correct 209 ms 50036 KB Output is correct
7 Correct 197 ms 49964 KB Output is correct
8 Correct 195 ms 49972 KB Output is correct
9 Correct 209 ms 50004 KB Output is correct
10 Correct 189 ms 49884 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 4 ms 10452 KB Output is correct
3 Correct 151 ms 45976 KB Output is correct
4 Correct 327 ms 46112 KB Output is correct
5 Correct 634 ms 45956 KB Output is correct
6 Correct 1149 ms 45980 KB Output is correct
7 Correct 2269 ms 46008 KB Output is correct
8 Correct 4813 ms 46004 KB Output is correct
9 Correct 3912 ms 46652 KB Output is correct
10 Correct 2496 ms 47040 KB Output is correct
11 Correct 2567 ms 46832 KB Output is correct
12 Correct 2509 ms 47052 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 4 ms 10452 KB Output is correct
3 Correct 202 ms 49916 KB Output is correct
4 Correct 202 ms 50016 KB Output is correct
5 Correct 222 ms 50000 KB Output is correct
6 Correct 206 ms 49992 KB Output is correct
7 Correct 193 ms 49968 KB Output is correct
8 Correct 209 ms 50036 KB Output is correct
9 Correct 197 ms 49964 KB Output is correct
10 Correct 195 ms 49972 KB Output is correct
11 Correct 209 ms 50004 KB Output is correct
12 Correct 189 ms 49884 KB Output is correct
13 Correct 151 ms 45976 KB Output is correct
14 Correct 327 ms 46112 KB Output is correct
15 Correct 634 ms 45956 KB Output is correct
16 Correct 1149 ms 45980 KB Output is correct
17 Correct 2269 ms 46008 KB Output is correct
18 Correct 4813 ms 46004 KB Output is correct
19 Correct 3912 ms 46652 KB Output is correct
20 Correct 2496 ms 47040 KB Output is correct
21 Correct 2567 ms 46832 KB Output is correct
22 Correct 2509 ms 47052 KB Output is correct
23 Correct 2145 ms 47012 KB Output is correct
24 Correct 1163 ms 47260 KB Output is correct
25 Correct 766 ms 47268 KB Output is correct
26 Correct 485 ms 47288 KB Output is correct
27 Correct 381 ms 47500 KB Output is correct
28 Correct 252 ms 47908 KB Output is correct
29 Correct 250 ms 48348 KB Output is correct
30 Correct 205 ms 49156 KB Output is correct
31 Correct 202 ms 49680 KB Output is correct
32 Correct 203 ms 49900 KB Output is correct