oj.uz

Submission #162691

# Submission time Handle Problem Language Result Execution time Memory
162691 2019-11-09T11:13:04 Z cerberus Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 1907 ms 48272 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 = 200, 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 288 ms 26592 KB Output is correct
2 Correct 307 ms 26820 KB Output is correct
3 Correct 301 ms 26592 KB Output is correct
4 Correct 289 ms 26736 KB Output is correct
5 Correct 295 ms 26624 KB Output is correct
6 Correct 298 ms 26724 KB Output is correct
7 Correct 306 ms 26724 KB Output is correct
8 Correct 290 ms 26720 KB Output is correct
9 Correct 299 ms 26712 KB Output is correct
10 Correct 298 ms 26620 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 230 ms 24028 KB Output is correct
4 Correct 273 ms 25032 KB Output is correct
5 Correct 321 ms 26472 KB Output is correct
6 Correct 385 ms 29104 KB Output is correct
7 Correct 572 ms 34148 KB Output is correct
8 Correct 1122 ms 48272 KB Output is correct
9 Correct 1907 ms 28388 KB Output is correct
10 Correct 1301 ms 23904 KB Output is correct
11 Correct 1233 ms 27880 KB Output is correct
12 Correct 1314 ms 27984 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 288 ms 26592 KB Output is correct
4 Correct 307 ms 26820 KB Output is correct
5 Correct 301 ms 26592 KB Output is correct
6 Correct 289 ms 26736 KB Output is correct
7 Correct 295 ms 26624 KB Output is correct
8 Correct 298 ms 26724 KB Output is correct
9 Correct 306 ms 26724 KB Output is correct
10 Correct 290 ms 26720 KB Output is correct
11 Correct 299 ms 26712 KB Output is correct
12 Correct 298 ms 26620 KB Output is correct
13 Correct 230 ms 24028 KB Output is correct
14 Correct 273 ms 25032 KB Output is correct
15 Correct 321 ms 26472 KB Output is correct
16 Correct 385 ms 29104 KB Output is correct
17 Correct 572 ms 34148 KB Output is correct
18 Correct 1122 ms 48272 KB Output is correct
19 Correct 1907 ms 28388 KB Output is correct
20 Correct 1301 ms 23904 KB Output is correct
21 Correct 1233 ms 27880 KB Output is correct
22 Correct 1314 ms 27984 KB Output is correct
23 Correct 1137 ms 28132 KB Output is correct
24 Correct 602 ms 28128 KB Output is correct
25 Correct 472 ms 28132 KB Output is correct
26 Correct 409 ms 28152 KB Output is correct
27 Correct 410 ms 28372 KB Output is correct
28 Correct 304 ms 29028 KB Output is correct
29 Correct 308 ms 29412 KB Output is correct
30 Correct 314 ms 30308 KB Output is correct
31 Correct 312 ms 30588 KB Output is correct
32 Correct 306 ms 30916 KB Output is correct