oj.uz

Submission #151179

# Submission time Handle Problem Language Result Execution time Memory
151179 2019-09-02T04:06:15 Z imyujin Trip to the Galapagos Islands (FXCUP4_island) C++17
31 / 100
 294 ms 24548 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 = node[0][j] + 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 = node[0].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));
      ~~~^~~~~~~~~~~~~~~~
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:74:25: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
    for(int j = node[0][j] + 1; j < N; j++) {
                         ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 24160 KB Output is correct
2 Correct 294 ms 24184 KB Output is correct
3 Correct 250 ms 24548 KB Output is correct
4 Correct 235 ms 24548 KB Output is correct
5 Correct 266 ms 24324 KB Output is correct
6 Correct 239 ms 24040 KB Output is correct
7 Correct 253 ms 24448 KB Output is correct
8 Correct 246 ms 24200 KB Output is correct
9 Correct 249 ms 24416 KB Output is correct
10 Correct 241 ms 24160 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 Incorrect 174 ms 22168 KB Output isn't correct
4 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 249 ms 24160 KB Output is correct
4 Correct 294 ms 24184 KB Output is correct
5 Correct 250 ms 24548 KB Output is correct
6 Correct 235 ms 24548 KB Output is correct
7 Correct 266 ms 24324 KB Output is correct
8 Correct 239 ms 24040 KB Output is correct
9 Correct 253 ms 24448 KB Output is correct
10 Correct 246 ms 24200 KB Output is correct
11 Correct 249 ms 24416 KB Output is correct
12 Correct 241 ms 24160 KB Output is correct
13 Incorrect 174 ms 22168 KB Output isn't correct
14 Halted 0 ms 0 KB -