oj.uz

Submission #151173

# Submission time Handle Problem Language Result Execution time Memory
151173 2019-09-02T03:11:50 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 24808 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 MAXN = 100010;
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];
map<pii, int> mem;
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 Separate(int A, int B){
	if(A > B) swap(A, B);
	if(mem.find(make_pair(A, B)) != mem.end()) return mem[make_pair(A, 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(A > B) swap(A, B);
	return mem[make_pair(A, B)] = ans + 1;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:75: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 281 ms 24380 KB Output is correct
2 Correct 286 ms 24376 KB Output is correct
3 Correct 279 ms 24632 KB Output is correct
4 Correct 286 ms 24808 KB Output is correct
5 Correct 283 ms 24512 KB Output is correct
6 Correct 272 ms 24368 KB Output is correct
7 Correct 280 ms 24632 KB Output is correct
8 Correct 273 ms 24288 KB Output is correct
9 Correct 299 ms 24616 KB Output is correct
10 Correct 290 ms 24424 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 7388 KB Output is correct
3 Correct 191 ms 21320 KB Output is correct
4 Correct 391 ms 21348 KB Output is correct
5 Correct 840 ms 21304 KB Output is correct
6 Correct 1518 ms 21152 KB Output is correct
7 Correct 3099 ms 20964 KB Output is correct
8 Execution timed out 5013 ms 21060 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 7416 KB Output is correct
2 Correct 8 ms 7388 KB Output is correct
3 Correct 281 ms 24380 KB Output is correct
4 Correct 286 ms 24376 KB Output is correct
5 Correct 279 ms 24632 KB Output is correct
6 Correct 286 ms 24808 KB Output is correct
7 Correct 283 ms 24512 KB Output is correct
8 Correct 272 ms 24368 KB Output is correct
9 Correct 280 ms 24632 KB Output is correct
10 Correct 273 ms 24288 KB Output is correct
11 Correct 299 ms 24616 KB Output is correct
12 Correct 290 ms 24424 KB Output is correct
13 Correct 191 ms 21320 KB Output is correct
14 Correct 391 ms 21348 KB Output is correct
15 Correct 840 ms 21304 KB Output is correct
16 Correct 1518 ms 21152 KB Output is correct
17 Correct 3099 ms 20964 KB Output is correct
18 Execution timed out 5013 ms 21060 KB Time limit exceeded
19 Halted 0 ms 0 KB -