oj.uz

Submission #151193

# Submission time Handle Problem Language Result Execution time Memory
151193 2019-09-02T05:29:24 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 977 ms 29412 KB 
#include "island.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

#define eb emplace_back
#define allv(v) ((v).begin()),((v).end())

const int X = 250;
const int MAXN = 100010;
const int NDIVX = 405;
const int MAXM = 300010;
const int LOGN = 17;

int N, M;
vector<int> node[MAXN], ed[MAXN];
int uni[MAXN];
vector<int> idx[MAXN];
int mem[NDIVX][MAXN];
int bigidx[MAXN];
int seg[LOGN][MAXN];

int level(int x) { return 31 - __builtin_clz(x); }

int guni(int x) { return x == uni[x] ? x : guni(uni[x]); }

void mkseg(int N) {
	for(int i = 0; i < N; i++) seg[0][i] = ed[0][i];
	for(int i = 1; i < LOGN; i++) for(int j = 0; j <= N - (1 << i); j++) 
		seg[i][j] = min(seg[i - 1][j], seg[i - 1][j + (1 << (i - 1))]);
}

int gseg(int x, int y) {
	int l = level(y - x + 1);
	return min(seg[l][x], seg[l][y - (1 << l) + 1]);
}

void Init(int K, vector<int> F, vector<int> S, vector<int> E){
	N = F.size();
	M = S.size();
	for(int i = 0; i < N; i++) {
		uni[i] = i;
		node[i].eb(i);
	}

	for(int i = M - 1; i >= 0; i--) {
		S[i] = guni(S[i]);
		E[i] = guni(E[i]);
		if(S[i] == E[i]) continue;
		if(node[S[i]].size() < node[E[i]].size()) swap(S[i], E[i]);
		node[S[i]].insert(node[S[i]].end(), allv(node[E[i]]));
		ed[S[i]].eb(i);
		ed[S[i]].insert(ed[S[i]].end(), allv(ed[E[i]]));
		uni[E[i]] = S[i];
	}
	for(int i = 0; i < N; i++) if(i == uni[i]) {
		node[0] = node[i];
		ed[0] = ed[i];
	}
	for(int i = 0; i < N; i++) idx[F[node[0][i]]].eb(i);
	mkseg(N - 1);

	int cnt = 0;
	for(int i = 0; i < K; i++) {
		if(idx[i].size() > X) {
			bigidx[i] = cnt++;
			int mn = M;
			for(int j = idx[i][0] + 1; j < N; j++) {
				mn = min(mn, ed[0][j - 1]);
				if(F[node[0][j]] == i) mn = M;
				else mem[bigidx[i]][F[node[0][j]]] = max(mem[bigidx[i]][F[node[0][j]]], mn);
			}
			mn = M;
			for(int j = idx[i].back() - 1; j >= 0; j--) {
				mn = min(mn, ed[0][j]);
				if(F[node[0][j]] == i) mn = M;
				else mem[bigidx[i]][F[node[0][j]]] = max(mem[bigidx[i]][F[node[0][j]]], mn);
			}
		}
		else bigidx[i] = -1;
	}
}

int Separate(int A, int B){
	if(bigidx[A] != -1) return mem[bigidx[A]][B] + 1;
	if(bigidx[B] != -1) return mem[bigidx[B]][A] + 1;

	int ans = 0;
	int pa = 0, pb = 0;
	while(pa < idx[A].size() && pb < idx[B].size()) {
		if(idx[A][pa] < idx[B][pb]) {
			if(pa == idx[A].size() - 1 || idx[A][pa + 1] > idx[B][pb])
				ans = max(ans, gseg(idx[A][pa], idx[B][pb] - 1));
			pa++;
		}
		else {
			if(pb == idx[B].size() - 1 || idx[B][pb + 1] > idx[A][pa])
				ans = max(ans, gseg(idx[B][pb], idx[A][pa] - 1));
			pb++;
		}
	}
	return ans + 1;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:91:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
        ~~~^~~~~~~~~~~~~~~
island.cpp:91:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
                              ~~~^~~~~~~~~~~~~~~
island.cpp:93:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pa == idx[A].size() - 1 || idx[A][pa + 1] > idx[B][pb])
       ~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:98:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pb == idx[B].size() - 1 || idx[B][pb + 1] > idx[A][pa])
       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 29156 KB Output is correct
2 Correct 224 ms 29008 KB Output is correct
3 Correct 231 ms 29408 KB Output is correct
4 Correct 221 ms 29412 KB Output is correct
5 Correct 222 ms 29380 KB Output is correct
6 Correct 218 ms 29028 KB Output is correct
7 Correct 344 ms 29400 KB Output is correct
8 Correct 232 ms 29088 KB Output is correct
9 Correct 246 ms 29412 KB Output is correct
10 Correct 249 ms 29408 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 195 ms 26348 KB Output is correct
4 Correct 219 ms 26580 KB Output is correct
5 Correct 277 ms 26728 KB Output is correct
6 Correct 364 ms 26540 KB Output is correct
7 Correct 539 ms 26752 KB Output is correct
8 Correct 977 ms 27384 KB Output is correct
9 Correct 390 ms 26212 KB Output is correct
10 Correct 319 ms 26144 KB Output is correct
11 Correct 317 ms 26340 KB Output is correct
12 Correct 348 ms 26468 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 232 ms 29156 KB Output is correct
4 Correct 224 ms 29008 KB Output is correct
5 Correct 231 ms 29408 KB Output is correct
6 Correct 221 ms 29412 KB Output is correct
7 Correct 222 ms 29380 KB Output is correct
8 Correct 218 ms 29028 KB Output is correct
9 Correct 344 ms 29400 KB Output is correct
10 Correct 232 ms 29088 KB Output is correct
11 Correct 246 ms 29412 KB Output is correct
12 Correct 249 ms 29408 KB Output is correct
13 Correct 195 ms 26348 KB Output is correct
14 Correct 219 ms 26580 KB Output is correct
15 Correct 277 ms 26728 KB Output is correct
16 Correct 364 ms 26540 KB Output is correct
17 Correct 539 ms 26752 KB Output is correct
18 Correct 977 ms 27384 KB Output is correct
19 Correct 390 ms 26212 KB Output is correct
20 Correct 319 ms 26144 KB Output is correct
21 Correct 317 ms 26340 KB Output is correct
22 Correct 348 ms 26468 KB Output is correct
23 Correct 353 ms 26568 KB Output is correct
24 Correct 242 ms 26336 KB Output is correct
25 Correct 229 ms 26516 KB Output is correct
26 Correct 238 ms 26292 KB Output is correct
27 Correct 208 ms 26924 KB Output is correct
28 Correct 221 ms 27020 KB Output is correct
29 Correct 225 ms 27364 KB Output is correct
30 Correct 224 ms 28644 KB Output is correct
31 Correct 228 ms 29132 KB Output is correct
32 Correct 237 ms 29096 KB Output is correct