oj.uz

Submission #151172

# Submission time Handle Problem Language Result Execution time Memory
151172 2019-09-02T03:04:31 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 25380 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 << 20;

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].push_back(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]].push_back(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]]].push_back(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 283 ms 24636 KB Output is correct
2 Correct 282 ms 24852 KB Output is correct
3 Correct 285 ms 25380 KB Output is correct
4 Correct 280 ms 25260 KB Output is correct
5 Correct 277 ms 25100 KB Output is correct
6 Correct 277 ms 24792 KB Output is correct
7 Correct 278 ms 25216 KB Output is correct
8 Correct 272 ms 24856 KB Output is correct
9 Correct 278 ms 25076 KB Output is correct
10 Correct 281 ms 24820 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 195 ms 21192 KB Output is correct
4 Correct 390 ms 21996 KB Output is correct
5 Correct 790 ms 21864 KB Output is correct
6 Correct 1501 ms 21604 KB Output is correct
7 Correct 3061 ms 21348 KB Output is correct
8 Execution timed out 5017 ms 21724 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 283 ms 24636 KB Output is correct
4 Correct 282 ms 24852 KB Output is correct
5 Correct 285 ms 25380 KB Output is correct
6 Correct 280 ms 25260 KB Output is correct
7 Correct 277 ms 25100 KB Output is correct
8 Correct 277 ms 24792 KB Output is correct
9 Correct 278 ms 25216 KB Output is correct
10 Correct 272 ms 24856 KB Output is correct
11 Correct 278 ms 25076 KB Output is correct
12 Correct 281 ms 24820 KB Output is correct
13 Correct 195 ms 21192 KB Output is correct
14 Correct 390 ms 21996 KB Output is correct
15 Correct 790 ms 21864 KB Output is correct
16 Correct 1501 ms 21604 KB Output is correct
17 Correct 3061 ms 21348 KB Output is correct
18 Execution timed out 5017 ms 21724 KB Time limit exceeded
19 Halted 0 ms 0 KB -