oj.uz

Submission #151171

# Submission time Handle Problem Language Result Execution time Memory
151171 2019-09-02T02:40:54 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
0 / 100
 5000 ms 83504 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 = 1000010;
const int MAXM = 3000010;
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(node[S[i]], node[E[i]]);
			swap(ed[S[i]], ed[E[i]]);
		}
		node[S[i]].insert(node[S[i]].end(), node[E[i]].begin(), node[E[i]].end());
		ed[S[i]].push_back(i);
		ed[S[i]].insert(ed[S[i]].end(), ed[E[i]].begin(), ed[E[i]].end());
		uni[E[i]] = S[i];
	}
	int r = 0;
	for(int i = 0; i < N; i++) if(i == uni[i]) r = i;
	swap(node[0], node[r]);
	swap(ed[0], ed[r]);
	for(int i = 0; i < N; i++) idx[F[node[0][i]]].push_back(i);
	for(int i = 0; i < K; i++) sort(allv(idx[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:79: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
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 83504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB Output is correct
2 Correct 68 ms 70824 KB Output is correct
3 Execution timed out 5066 ms 83368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 70776 KB Output is correct
2 Correct 68 ms 70824 KB Output is correct
3 Execution timed out 5037 ms 83504 KB Time limit exceeded
4 Halted 0 ms 0 KB -