oj.uz

Submission #162689

# Submission time Handle Problem Language Result Execution time Memory
162689 2019-11-09T11:01:44 Z cerberus Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 84644 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 = 180, 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 360 ms 30820 KB Output is correct
2 Correct 350 ms 30912 KB Output is correct
3 Correct 408 ms 30888 KB Output is correct
4 Correct 364 ms 30944 KB Output is correct
5 Correct 365 ms 31000 KB Output is correct
6 Correct 366 ms 30876 KB Output is correct
7 Correct 379 ms 30780 KB Output is correct
8 Correct 358 ms 30820 KB Output is correct
9 Correct 351 ms 30944 KB Output is correct
10 Correct 354 ms 30816 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 283 ms 82424 KB Output is correct
4 Correct 302 ms 82528 KB Output is correct
5 Correct 378 ms 82660 KB Output is correct
6 Correct 374 ms 82784 KB Output is correct
7 Correct 440 ms 83040 KB Output is correct
8 Correct 639 ms 83940 KB Output is correct
9 Correct 2864 ms 84644 KB Output is correct
10 Execution timed out 5088 ms 27940 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 360 ms 30820 KB Output is correct
4 Correct 350 ms 30912 KB Output is correct
5 Correct 408 ms 30888 KB Output is correct
6 Correct 364 ms 30944 KB Output is correct
7 Correct 365 ms 31000 KB Output is correct
8 Correct 366 ms 30876 KB Output is correct
9 Correct 379 ms 30780 KB Output is correct
10 Correct 358 ms 30820 KB Output is correct
11 Correct 351 ms 30944 KB Output is correct
12 Correct 354 ms 30816 KB Output is correct
13 Correct 283 ms 82424 KB Output is correct
14 Correct 302 ms 82528 KB Output is correct
15 Correct 378 ms 82660 KB Output is correct
16 Correct 374 ms 82784 KB Output is correct
17 Correct 440 ms 83040 KB Output is correct
18 Correct 639 ms 83940 KB Output is correct
19 Correct 2864 ms 84644 KB Output is correct
20 Execution timed out 5088 ms 27940 KB Time limit exceeded
21 Halted 0 ms 0 KB -