oj.uz

Submission #151183

# Submission time Handle Problem Language Result Execution time Memory
151183 2019-09-02T04:27:20 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 5000 ms 24500 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][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;
	
	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));
	}
	return ans + 1;
}

Compilation message

island.cpp: In function 'int Separate(int, int)':
island.cpp:98: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 242 ms 24136 KB Output is correct
2 Correct 244 ms 24140 KB Output is correct
3 Correct 241 ms 24420 KB Output is correct
4 Correct 238 ms 24420 KB Output is correct
5 Correct 249 ms 24440 KB Output is correct
6 Correct 246 ms 24160 KB Output is correct
7 Correct 244 ms 24500 KB Output is correct
8 Correct 242 ms 24132 KB Output is correct
9 Correct 242 ms 24416 KB Output is correct
10 Correct 245 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 8 ms 7544 KB Output is correct
3 Correct 181 ms 21508 KB Output is correct
4 Correct 212 ms 21480 KB Output is correct
5 Correct 272 ms 21656 KB Output is correct
6 Correct 355 ms 21472 KB Output is correct
7 Correct 537 ms 21620 KB Output is correct
8 Correct 1008 ms 23376 KB Output is correct
9 Execution timed out 5089 ms 21220 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 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 242 ms 24136 KB Output is correct
4 Correct 244 ms 24140 KB Output is correct
5 Correct 241 ms 24420 KB Output is correct
6 Correct 238 ms 24420 KB Output is correct
7 Correct 249 ms 24440 KB Output is correct
8 Correct 246 ms 24160 KB Output is correct
9 Correct 244 ms 24500 KB Output is correct
10 Correct 242 ms 24132 KB Output is correct
11 Correct 242 ms 24416 KB Output is correct
12 Correct 245 ms 24216 KB Output is correct
13 Correct 181 ms 21508 KB Output is correct
14 Correct 212 ms 21480 KB Output is correct
15 Correct 272 ms 21656 KB Output is correct
16 Correct 355 ms 21472 KB Output is correct
17 Correct 537 ms 21620 KB Output is correct
18 Correct 1008 ms 23376 KB Output is correct
19 Execution timed out 5089 ms 21220 KB Time limit exceeded
20 Halted 0 ms 0 KB -