oj.uz

Submission #151189

# Submission time Handle Problem Language Result Execution time Memory
151189 2019-09-02T04:47:51 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 24408 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 MX = 1 << 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[2 * MX];

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

void mkseg(int idx, int l, int r) {
	if(l == r) seg[idx] = ed[0][l];
	else {
		int m = (l + r) / 2;
		mkseg(idx * 2, l, m);
		mkseg(idx * 2 + 1, m + 1, r);
		seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
	}
}

int gseg(int idx, int l, int r, int x, int y) {
	if(x <= l && r <= y) return seg[idx];
	else if(r < x || y < l) return M;
	int m = (l + r) / 2;
	return min(gseg(idx * 2, l, m, x, y), gseg(idx * 2 + 1, m + 1, r, x, y));
}
int gseg(int x, int y) { return gseg(1, 0, N - 2, x, y); }

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(1, 0, N - 2);

	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]) {
			ans = max(ans, gseg(idx[A][pa], idx[B][pb] - 1));
			pa++;
		}
		else {
			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:96:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
        ~~~^~~~~~~~~~~~~~~
island.cpp:96:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
                              ~~~^~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 23952 KB Output is correct
2 Correct 241 ms 24036 KB Output is correct
3 Correct 235 ms 24292 KB Output is correct
4 Correct 240 ms 24232 KB Output is correct
5 Correct 256 ms 24260 KB Output is correct
6 Correct 232 ms 24068 KB Output is correct
7 Correct 231 ms 24408 KB Output is correct
8 Correct 235 ms 24036 KB Output is correct
9 Correct 242 ms 24292 KB Output is correct
10 Correct 230 ms 23896 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 182 ms 21408 KB Output is correct
4 Correct 210 ms 21348 KB Output is correct
5 Correct 264 ms 21548 KB Output is correct
6 Correct 350 ms 21344 KB Output is correct
7 Correct 525 ms 21540 KB Output is correct
8 Correct 1002 ms 22384 KB Output is correct
9 Execution timed out 5042 ms 21092 KB Time limit exceeded
10 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 245 ms 23952 KB Output is correct
4 Correct 241 ms 24036 KB Output is correct
5 Correct 235 ms 24292 KB Output is correct
6 Correct 240 ms 24232 KB Output is correct
7 Correct 256 ms 24260 KB Output is correct
8 Correct 232 ms 24068 KB Output is correct
9 Correct 231 ms 24408 KB Output is correct
10 Correct 235 ms 24036 KB Output is correct
11 Correct 242 ms 24292 KB Output is correct
12 Correct 230 ms 23896 KB Output is correct
13 Correct 182 ms 21408 KB Output is correct
14 Correct 210 ms 21348 KB Output is correct
15 Correct 264 ms 21548 KB Output is correct
16 Correct 350 ms 21344 KB Output is correct
17 Correct 525 ms 21540 KB Output is correct
18 Correct 1002 ms 22384 KB Output is correct
19 Execution timed out 5042 ms 21092 KB Time limit exceeded
20 Halted 0 ms 0 KB -