oj.uz

Submission #151174

# Submission time Handle Problem Language Result Execution time Memory
151174 2019-09-02T03:42:12 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 24676 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 SQRTN = 320;
const int MAXN = SQRTN * SQRTN;
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[SQRTN][SQRTN];
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++) bigidx[i] = idx[i].size() > SQRTN ? cnt++ : -1;
	for(int i = 0; i < cnt; i++) for(int j = 0; j < cnt; j++) mem[i][j] = -1;
}

int Separate(int A, int B){
	if(bigidx[A] != -1 && bigidx[B] != -1 && mem[bigidx[A]][bigidx[B]] != -1) return mem[bigidx[A]][bigidx[B]];
	if(idx[A].size() > idx[B].size()) swap(A, B);
	int ans = 0;
	for(auto a : idx[A]) {
		int lb = lower_bound(allv(idx[B]), a) - idx[B].begin();
		if(lb != 0) ans = max(ans, gseg(idx[B][lb - 1], a - 1));
		if(lb != idx[B].size()) ans = max(ans, gseg(a, idx[B][lb] - 1));
	}
	if(bigidx[A] != -1 && bigidx[B] != -1) mem[bigidx[A]][bigidx[B]] = mem[bigidx[B]][bigidx[A]] = ans + 1;
	return ans + 1;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:80:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(lb != idx[B].size()) ans = max(ans, gseg(a, idx[B][lb] - 1));
      ~~~^~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 24140 KB Output is correct
2 Correct 242 ms 24164 KB Output is correct
3 Correct 235 ms 24464 KB Output is correct
4 Correct 241 ms 24528 KB Output is correct
5 Correct 247 ms 24292 KB Output is correct
6 Correct 238 ms 24164 KB Output is correct
7 Correct 251 ms 24676 KB Output is correct
8 Correct 239 ms 24196 KB Output is correct
9 Correct 231 ms 24420 KB Output is correct
10 Correct 257 ms 24216 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 9 ms 7508 KB Output is correct
3 Correct 201 ms 21360 KB Output is correct
4 Correct 420 ms 21476 KB Output is correct
5 Correct 895 ms 21564 KB Output is correct
6 Correct 1689 ms 21348 KB Output is correct
7 Correct 3436 ms 21216 KB Output is correct
8 Execution timed out 5010 ms 21524 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 9 ms 7508 KB Output is correct
3 Correct 241 ms 24140 KB Output is correct
4 Correct 242 ms 24164 KB Output is correct
5 Correct 235 ms 24464 KB Output is correct
6 Correct 241 ms 24528 KB Output is correct
7 Correct 247 ms 24292 KB Output is correct
8 Correct 238 ms 24164 KB Output is correct
9 Correct 251 ms 24676 KB Output is correct
10 Correct 239 ms 24196 KB Output is correct
11 Correct 231 ms 24420 KB Output is correct
12 Correct 257 ms 24216 KB Output is correct
13 Correct 201 ms 21360 KB Output is correct
14 Correct 420 ms 21476 KB Output is correct
15 Correct 895 ms 21564 KB Output is correct
16 Correct 1689 ms 21348 KB Output is correct
17 Correct 3436 ms 21216 KB Output is correct
18 Execution timed out 5010 ms 21524 KB Time limit exceeded
19 Halted 0 ms 0 KB -