oj.uz

Submission #151187

# Submission time Handle Problem Language Result Execution time Memory
151187 2019-09-02T04:46:04 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 24360 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 = 280;
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];
int mem[SQRTN][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() > SQRTN) {
			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:95:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
        ~~~^~~~~~~~~~~~~~~
island.cpp:95: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 233 ms 23908 KB Output is correct
2 Correct 236 ms 23956 KB Output is correct
3 Correct 243 ms 24336 KB Output is correct
4 Correct 239 ms 24292 KB Output is correct
5 Correct 238 ms 24360 KB Output is correct
6 Correct 234 ms 23908 KB Output is correct
7 Correct 242 ms 24288 KB Output is correct
8 Correct 268 ms 23956 KB Output is correct
9 Correct 244 ms 24292 KB Output is correct
10 Correct 241 ms 24000 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 177 ms 21220 KB Output is correct
4 Correct 211 ms 21416 KB Output is correct
5 Correct 262 ms 21548 KB Output is correct
6 Correct 367 ms 21388 KB Output is correct
7 Correct 541 ms 21440 KB Output is correct
8 Correct 967 ms 22292 KB Output is correct
9 Execution timed out 5020 ms 21224 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 233 ms 23908 KB Output is correct
4 Correct 236 ms 23956 KB Output is correct
5 Correct 243 ms 24336 KB Output is correct
6 Correct 239 ms 24292 KB Output is correct
7 Correct 238 ms 24360 KB Output is correct
8 Correct 234 ms 23908 KB Output is correct
9 Correct 242 ms 24288 KB Output is correct
10 Correct 268 ms 23956 KB Output is correct
11 Correct 244 ms 24292 KB Output is correct
12 Correct 241 ms 24000 KB Output is correct
13 Correct 177 ms 21220 KB Output is correct
14 Correct 211 ms 21416 KB Output is correct
15 Correct 262 ms 21548 KB Output is correct
16 Correct 367 ms 21388 KB Output is correct
17 Correct 541 ms 21440 KB Output is correct
18 Correct 967 ms 22292 KB Output is correct
19 Execution timed out 5020 ms 21224 KB Time limit exceeded
20 Halted 0 ms 0 KB -