oj.uz

Submission #150770

# Submission time Handle Problem Language Result Execution time Memory
150770 2019-09-01T08:54:48 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 205 ms 74852 KB 
#include <bits/stdc++.h>

using namespace std;

#include "island.h"

#define MAGIC 175

int par[175][100005];
vector<int> ss ,ee;
int M;

int find(int a, int b) {
	return par[a][b] == b ? b : par[a][b] = find(a, par[a][b]);
}

vector<pair<int, int>> v;

int findd(int a, int b) {
	if (par[a][b] == b)
		return b;
	v.emplace_back(b, par[a][b]);
	return par[a][b] = find(a, par[a][b]);
}

void Init(int k, std::vector<int> F, std::vector<int> S, std::vector<int> E){
	int N = F.size();
	M = S.size();
	reverse(S.begin(), S.end());
	reverse(E.begin(), E.end());
	for (int i = 0; i < k; i++)
		par[0][i] = par[1][i] = i;
	for (int i = 0; i < M; i++) {
		int at = i / MAGIC + 1;
		S[i] = F[S[i]];
		E[i] = F[E[i]];
		// printf(" %d %d\n", S[i], E[i]);
		int ta = find(at, S[i]);
		int tb = find(at, E[i]);
		if (ta != tb)
			par[at][ta] = tb;
		if (at != (i + 1) / MAGIC + 1 || i == M - 1)
			for (int j = 0; j < k; j++)
				par[at + 1][j] = find(at, j);
	}
	ss = S, ee =E;
}

int Separate(int A, int B){
	// printf("Q %d %d\n", A, B);
	int lo = 0, hi = (M - 1) / MAGIC + 2;
	while (lo < hi) {
		int mi = (lo + hi) / 2;
		if (par[mi][A] == par[mi][B])
			hi = mi;
		else
			lo = mi + 1;
	}
	lo--;
	int at = lo * MAGIC;
	if (lo == (M - 1) / MAGIC + 1)
		return 0;
	int to = min(at + MAGIC, M);
	int ans = M;
	for (int i = at; i < to; i++) {
		int ta = findd(lo, ss[i]);
		int tb = findd(lo, ee[i]);
		if (ta != tb) {
			v.emplace_back(ta, par[lo][ta]);
			par[lo][ta] = tb;
		}
		if (findd(lo, A) == findd(lo, B)){
			ans = i;
			break;
		}
	}
	while (!v.empty()) {
		par[lo][v.back().first] = v.back().second;
		v.pop_back();
	}
	return M - ans;
}

Compilation message

island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:27:6: warning: unused variable 'N' [-Wunused-variable]
  int N = F.size();
      ^

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 74852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -