oj.uz

Submission #162692

# Submission time Handle Problem Language Result Execution time Memory
162692 2019-11-09T11:17:52 Z cerberus Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 2858 ms 82276 KB 
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include "island.h"

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 10, M = 3e5 + 10, S = 110, BIG = N / S + 5;

int n, m;
int par[N], sz[N], max_seen[N];
vector<int> in_comp[N], at_islands[N];
vector<pii> roots[N];

int big_finch_id[N], big_precomp[BIG][N];
vector<int> big_finches;
bool is_big_finch[N], big_finches_done[BIG][N];

int get_root(int u);
void merge(int u, int v, int id, vector<int> &f);

void Init(int k, std::vector<int> f, std::vector<int> eu, std::vector<int> ev) {
	// cout << (sizeof(big_finches_done) + sizeof(big_precomp)) / 1e6 << endl;
	n = f.size(); m = eu.size();
	for (int i = 0; i < n; ++i) {
		par[i] = i;
		sz[i] = 1;
		in_comp[i] = {i};
		roots[i].pb({m, i});
		at_islands[f[i]].pb(i);
	}
	for (int i = 0; i < k; ++i) {
		if (at_islands[i].size() >= S) {
			big_finch_id[i] = big_finches.size();
			big_finches.pb(i);
			is_big_finch[i] = true;
			for (auto &u : at_islands[i]) {
				big_finches_done[big_finch_id[i]][u] = true;
				big_precomp[big_finch_id[i]][f[u]] = m;
			}
		}
	}
	for (int i = m - 1; i >= 0; --i) {
		merge(eu[i], ev[i], i, f);
	}
}

int Separate(int A, int B) {
	if (at_islands[A].size() < at_islands[B].size()) {
		swap(A, B);
	}
	if (is_big_finch[A]) {
		return big_precomp[big_finch_id[A]][B] + 1;
	} else {
		int ans = 1;
		for (auto &u : at_islands[A]) {
			for (auto &p : roots[u]) {
				max_seen[p.second] = max(max_seen[p.second], p.first);
			}
		}
		for (auto &v : at_islands[B]) {
			for (auto &p : roots[v]) {
				auto cand = min(max_seen[p.second], p.first) + 1;
				ans = max(ans, cand);
			}
		}
		for (auto &u : at_islands[A]) {
			for (auto &p : roots[u]) {
				max_seen[p.second] = 0;
			}
		}
		return ans;
	}
	return 0;
}

int get_root(int u) {
	if (u != par[u]) {
		par[u] = get_root(par[u]);
	}
	return par[u];
}

void merge(int u, int v, int id, vector<int> &f) {
	u = get_root(u);
	v = get_root(v);
	if (u == v) {
		return;
	} else if (sz[u] < sz[v]) {
		swap(u, v);
	}
	for (auto &b : big_finches) {
		int add_to = -1, bid = big_finch_id[b];
		if (big_finches_done[bid][u] xor big_finches_done[bid][v]) {
			add_to = (big_finches_done[bid][u] ? v : u);
			big_finches_done[bid][add_to] = true;
			for (auto &w : in_comp[add_to]) {
				big_precomp[bid][f[w]] = max(big_precomp[bid][f[w]], id);
			}
		}
	}
	par[v] = u;
	sz[u] += sz[v];
	for (auto &w : in_comp[v]) {
		in_comp[u].pb(w);
		roots[w].pb({id, u});
	}
	in_comp[v].clear();
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 26564 KB Output is correct
2 Correct 309 ms 26568 KB Output is correct
3 Correct 306 ms 26564 KB Output is correct
4 Correct 299 ms 26724 KB Output is correct
5 Correct 307 ms 26636 KB Output is correct
6 Correct 290 ms 26780 KB Output is correct
7 Correct 332 ms 26612 KB Output is correct
8 Correct 292 ms 26596 KB Output is correct
9 Correct 291 ms 26600 KB Output is correct
10 Correct 306 ms 26624 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 210 ms 24036 KB Output is correct
4 Correct 259 ms 25100 KB Output is correct
5 Correct 315 ms 26340 KB Output is correct
6 Correct 388 ms 28936 KB Output is correct
7 Correct 570 ms 34276 KB Output is correct
8 Correct 1152 ms 48488 KB Output is correct
9 Correct 2858 ms 82276 KB Output is correct
10 Correct 1476 ms 41840 KB Output is correct
11 Correct 1507 ms 44084 KB Output is correct
12 Correct 1431 ms 41828 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 291 ms 26564 KB Output is correct
4 Correct 309 ms 26568 KB Output is correct
5 Correct 306 ms 26564 KB Output is correct
6 Correct 299 ms 26724 KB Output is correct
7 Correct 307 ms 26636 KB Output is correct
8 Correct 290 ms 26780 KB Output is correct
9 Correct 332 ms 26612 KB Output is correct
10 Correct 292 ms 26596 KB Output is correct
11 Correct 291 ms 26600 KB Output is correct
12 Correct 306 ms 26624 KB Output is correct
13 Correct 210 ms 24036 KB Output is correct
14 Correct 259 ms 25100 KB Output is correct
15 Correct 315 ms 26340 KB Output is correct
16 Correct 388 ms 28936 KB Output is correct
17 Correct 570 ms 34276 KB Output is correct
18 Correct 1152 ms 48488 KB Output is correct
19 Correct 2858 ms 82276 KB Output is correct
20 Correct 1476 ms 41840 KB Output is correct
21 Correct 1507 ms 44084 KB Output is correct
22 Correct 1431 ms 41828 KB Output is correct
23 Correct 985 ms 24420 KB Output is correct
24 Correct 518 ms 24164 KB Output is correct
25 Correct 447 ms 24036 KB Output is correct
26 Correct 360 ms 24160 KB Output is correct
27 Correct 352 ms 24168 KB Output is correct
28 Correct 282 ms 24772 KB Output is correct
29 Correct 273 ms 25184 KB Output is correct
30 Correct 302 ms 26088 KB Output is correct
31 Correct 315 ms 26544 KB Output is correct
32 Correct 294 ms 26596 KB Output is correct