oj.uz

Submission #162690

# Submission time Handle Problem Language Result Execution time Memory
162690 2019-11-09T11:02:47 Z cerberus Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 93560 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 = 150, BIG = N / S + 5;

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

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

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[u][big_finch_id[i]] = 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 lo = 1, hi = m - 1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			bool meet = false;
			vector<int> roots_a;
			for (auto &u : at_islands[A]) {
				auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
				roots_a.pb(it->second);
				have[it->second] = true;
			}
			for (auto &u : at_islands[B]) {
				auto it = upper_bound(roots[u].begin(), roots[u].end(), make_pair(mid, -1), greater<pii>()) - 1;
				if (have[it->second]) {
					meet = true;
					break;
				}
			}
			for (auto &r : roots_a) {
				have[r] = false;
			}
			if (meet) {
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
		return hi + 1;
	}
	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[u][bid] xor big_finches_done[v][bid]) {
			add_to = (big_finches_done[u][bid] ? v : u);
			big_finches_done[add_to][bid] = 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 369 ms 26600 KB Output is correct
2 Correct 352 ms 26592 KB Output is correct
3 Correct 363 ms 26660 KB Output is correct
4 Correct 359 ms 26748 KB Output is correct
5 Correct 367 ms 26676 KB Output is correct
6 Correct 727 ms 26592 KB Output is correct
7 Correct 365 ms 26596 KB Output is correct
8 Correct 359 ms 26592 KB Output is correct
9 Correct 355 ms 26596 KB Output is correct
10 Correct 352 ms 26592 KB Output is correct

Subtask #2
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 286 ms 89440 KB Output is correct
4 Correct 315 ms 89696 KB Output is correct
5 Correct 347 ms 89668 KB Output is correct
6 Correct 477 ms 89796 KB Output is correct
7 Correct 466 ms 90056 KB Output is correct
8 Correct 644 ms 91104 KB Output is correct
9 Correct 1092 ms 93560 KB Output is correct
10 Execution timed out 5099 ms 23888 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
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 369 ms 26600 KB Output is correct
4 Correct 352 ms 26592 KB Output is correct
5 Correct 363 ms 26660 KB Output is correct
6 Correct 359 ms 26748 KB Output is correct
7 Correct 367 ms 26676 KB Output is correct
8 Correct 727 ms 26592 KB Output is correct
9 Correct 365 ms 26596 KB Output is correct
10 Correct 359 ms 26592 KB Output is correct
11 Correct 355 ms 26596 KB Output is correct
12 Correct 352 ms 26592 KB Output is correct
13 Correct 286 ms 89440 KB Output is correct
14 Correct 315 ms 89696 KB Output is correct
15 Correct 347 ms 89668 KB Output is correct
16 Correct 477 ms 89796 KB Output is correct
17 Correct 466 ms 90056 KB Output is correct
18 Correct 644 ms 91104 KB Output is correct
19 Correct 1092 ms 93560 KB Output is correct
20 Execution timed out 5099 ms 23888 KB Time limit exceeded
21 Halted 0 ms 0 KB -