oj.uz

Submission #151180

# Submission time Handle Problem Language Result Execution time Memory
151180 2019-09-02T04:07:59 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 259 ms 24536 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++;
			for(int j = 0; j < N; j++) mem[bigidx[i]][j] = 0;
			int mn = M;
			for(int j = idx[i][0] + 1; j < N; j++) {
				mn = min(mn, ed[0][j - 1]);
				if(node[0][j] == i) mn = M;
				else mem[bigidx[i]][node[0][j]] = max(mem[bigidx[i]][node[0][j]], mn);
			}
			mn = M;
			for(int j = idx[i].back() - 1; j >= 0; j--) {
				mn = min(mn, ed[0][j]);
				if(node[0][j] == i) mn = M;
				else mem[bigidx[i]][node[0][j]] = max(mem[bigidx[i]][node[0][j]], mn);
			}
		}
		else bigidx[i] = -1;
	}

	for(int i = 0; i < cnt; i++) for(int j = 0; j < K; j++) mem[i][j] = -1;
}

int Separate(int A, int B){
	if(bigidx[A] != -1) return mem[bigidx[A]][B];
	if(bigidx[B] != -1) return mem[bigidx[B]][A];
	
	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:100: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 259 ms 24300 KB Output is correct
2 Correct 242 ms 24160 KB Output is correct
3 Correct 244 ms 24536 KB Output is correct
4 Correct 239 ms 24516 KB Output is correct
5 Correct 240 ms 24288 KB Output is correct
6 Correct 257 ms 24144 KB Output is correct
7 Correct 241 ms 24432 KB Output is correct
8 Correct 239 ms 24036 KB Output is correct
9 Correct 244 ms 24524 KB Output is correct
10 Correct 237 ms 24136 KB Output is correct

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Incorrect 204 ms 22180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 8 ms 7544 KB Output is correct
3 Correct 259 ms 24300 KB Output is correct
4 Correct 242 ms 24160 KB Output is correct
5 Correct 244 ms 24536 KB Output is correct
6 Correct 239 ms 24516 KB Output is correct
7 Correct 240 ms 24288 KB Output is correct
8 Correct 257 ms 24144 KB Output is correct
9 Correct 241 ms 24432 KB Output is correct
10 Correct 239 ms 24036 KB Output is correct
11 Correct 244 ms 24524 KB Output is correct
12 Correct 237 ms 24136 KB Output is correct
13 Incorrect 204 ms 22180 KB Output isn't correct
14 Halted 0 ms 0 KB -