Submission #151193

#	Time	Username	Problem	Language	Result	Execution time	Memory
151193		imyujin	Trip to the Galapagos Islands (FXCUP4_island)	C++17	100 / 100	977 ms	29412 KiB

island

#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 X = 250;
const int MAXN = 100010;
const int NDIVX = 405;
const int MAXM = 300010;
const int LOGN = 17;

int N, M;
vector<int> node[MAXN], ed[MAXN];
int uni[MAXN];
vector<int> idx[MAXN];
int mem[NDIVX][MAXN];
int bigidx[MAXN];
int seg[LOGN][MAXN];

int level(int x) { return 31 - __builtin_clz(x); }

int guni(int x) { return x == uni[x] ? x : guni(uni[x]); }

void mkseg(int N) {
	for(int i = 0; i < N; i++) seg[0][i] = ed[0][i];
	for(int i = 1; i < LOGN; i++) for(int j = 0; j <= N - (1 << i); j++) 
		seg[i][j] = min(seg[i - 1][j], seg[i - 1][j + (1 << (i - 1))]);
}

int gseg(int x, int y) {
	int l = level(y - x + 1);
	return min(seg[l][x], seg[l][y - (1 << l) + 1]);
}

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(N - 1);

	int cnt = 0;
	for(int i = 0; i < K; i++) {
		if(idx[i].size() > X) {
			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]) {
			if(pa == idx[A].size() - 1 || idx[A][pa + 1] > idx[B][pb])
				ans = max(ans, gseg(idx[A][pa], idx[B][pb] - 1));
			pa++;
		}
		else {
			if(pb == idx[B].size() - 1 || idx[B][pb + 1] > idx[A][pa])
				ans = max(ans, gseg(idx[B][pb], idx[A][pa] - 1));
			pb++;
		}
	}
	return ans + 1;
}

Compilation message (stderr)

island.cpp: In function 'int Separate(int, int)':
island.cpp:91:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
        ~~~^~~~~~~~~~~~~~~
island.cpp:91:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pa < idx[A].size() && pb < idx[B].size()) {
                              ~~~^~~~~~~~~~~~~~~
island.cpp:93:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pa == idx[A].size() - 1 || idx[A][pa + 1] > idx[B][pb])
       ~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:98:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(pb == idx[B].size() - 1 || idx[B][pb + 1] > idx[A][pa])
       ~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 39 / 39
• Subtask 3: 30 / 30