oj.uz

Submission #148012

# Submission time Handle Problem Language Result Execution time Memory
148012 2019-08-31T11:10:21 Z imsifile Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 2593 ms 22392 KB 
#include "island.h"
#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;
 
const int MINSZ = 200;
int N, K, bcn[100100], maj[100100], mcn;
vector<int> con[100100], mat[505];
 
int par[100100], pv[100100];
int root(int ix){
	if(par[ix]<0) return ix;
	int x=root(par[ix]);
	if(par[ix]!=x) pv[ix]=pv[par[ix]];
	par[ix]=x;
	return x;
}
 
int p2[200200], val[200200], lr[200200][2], vcn;
int poi[100100], pcn, edg[300000], ecn; vector<int> wid[100100];
int rt(int ix){ return p2[ix]<0 ? ix : p2[ix]=rt(p2[ix]); }
void dfs(int ix){
	if(ix<0) return;
	dfs(lr[ix][0]);
	if(val[ix]<0) edg[(1<<17) + ecn++] = -val[ix];
	else poi[pcn++] = val[ix];
	dfs(lr[ix][1]); // dist(s,e) = min(s..e)
}
 
void Init(int K_, vector<int> F, vector<int> S, vector<int> E){
	int M=S.size();
	N=F.size(), K=K_;
	memset(bcn, 0, sizeof(bcn)), mcn=vcn=pcn=ecn=0;
	for(int i=0; i<N; i++) con[F[i]].push_back(i), bcn[F[i]]++, maj[i]=-1;
	for(int i=0; i<K; i++){
		if(bcn[i]<MINSZ) continue;
		maj[i]=mcn;
		for(int j=0; j<=N; j++) par[j]=-1;
		for(int j=M-1; j>=0; j--){
			int s=S[j], e=E[j];
			if(F[s]==i) s=N;
			if(F[e]==i) e=N;
			s=root(s), e=root(e);
			if(s==e) continue;
			if(s==N) par[e]=s, pv[e]=j+1;
			else par[s]=e, pv[s]=j+1;
		}
		mat[mcn].resize(K,0);
		for(int j=0; j<N; j++){
			if(F[j]==i) continue;
			root(j);
			mat[mcn][F[j]] = max(mat[mcn][F[j]], pv[j]);
		}
		mcn++;
	}
	vcn=N;
	for(int i=0; i<N; i++) p2[i]=-1, val[i]=F[i], lr[i][0]=lr[i][1]=-1;
	for(int i=M-1; i>=0; i--){
		int s=rt(S[i]), e=rt(E[i]);
		if(s==e) continue;
		p2[vcn]=-1, val[vcn]=-(i+1), lr[vcn][0]=s, lr[vcn][1]=e;
		p2[s]=p2[e]=vcn++;
	}
	dfs(vcn-1);
	for(int i=(1<<17); --i;){
		if(edg[i*2+1]==0) edg[i]=edg[i*2];
		else edg[i]=min(edg[i*2],edg[i*2+1]);
	}
	for(int i=0; i<N; i++) wid[poi[i]].push_back(i);
}
 
int rmq(int s, int e){
	int mi=1<<20;
	s+=1<<17, e+=1<<17;
	while(s<=e){
		if(s&1) mi=min(mi,edg[s++]);
		if(e%2==0) mi=min(mi,edg[e--]);
		if(s>e) break;
		s>>=1, e>>=1;
	}
	return mi;
}
 
int Separate(int A, int B){
	if(maj[A]>=0) return mat[maj[A]][B];
	if(maj[B]>=0) return mat[maj[B]][A];
	int mx=0, asz=wid[A].size(), bsz=wid[B].size();
	for(int i=0, j=0; i<asz && j<bsz;){
		int s=wid[A][i], e=wid[B][j];
		if(s<e) mx=max(mx,rmq(s,e-1)), i++;
		else swap(s,e), mx=max(mx,rmq(s,e-1)), j++;
	}
	return mx;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 22368 KB Output is correct
2 Correct 237 ms 22372 KB Output is correct
3 Correct 249 ms 22372 KB Output is correct
4 Correct 245 ms 22372 KB Output is correct
5 Correct 252 ms 22264 KB Output is correct
6 Correct 237 ms 22368 KB Output is correct
7 Correct 264 ms 22392 KB Output is correct
8 Correct 251 ms 22336 KB Output is correct
9 Correct 300 ms 22372 KB Output is correct
10 Correct 284 ms 22244 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6016 KB Output is correct
2 Correct 11 ms 6016 KB Output is correct
3 Correct 197 ms 18168 KB Output is correct
4 Correct 265 ms 18044 KB Output is correct
5 Correct 435 ms 17764 KB Output is correct
6 Correct 666 ms 17852 KB Output is correct
7 Correct 1216 ms 17892 KB Output is correct
8 Correct 2593 ms 18020 KB Output is correct
9 Correct 2182 ms 18148 KB Output is correct
10 Correct 1396 ms 17144 KB Output is correct
11 Correct 1313 ms 17120 KB Output is correct
12 Correct 1318 ms 17120 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6016 KB Output is correct
2 Correct 11 ms 6016 KB Output is correct
3 Correct 239 ms 22368 KB Output is correct
4 Correct 237 ms 22372 KB Output is correct
5 Correct 249 ms 22372 KB Output is correct
6 Correct 245 ms 22372 KB Output is correct
7 Correct 252 ms 22264 KB Output is correct
8 Correct 237 ms 22368 KB Output is correct
9 Correct 264 ms 22392 KB Output is correct
10 Correct 251 ms 22336 KB Output is correct
11 Correct 300 ms 22372 KB Output is correct
12 Correct 284 ms 22244 KB Output is correct
13 Correct 197 ms 18168 KB Output is correct
14 Correct 265 ms 18044 KB Output is correct
15 Correct 435 ms 17764 KB Output is correct
16 Correct 666 ms 17852 KB Output is correct
17 Correct 1216 ms 17892 KB Output is correct
18 Correct 2593 ms 18020 KB Output is correct
19 Correct 2182 ms 18148 KB Output is correct
20 Correct 1396 ms 17144 KB Output is correct
21 Correct 1313 ms 17120 KB Output is correct
22 Correct 1318 ms 17120 KB Output is correct
23 Correct 1191 ms 17380 KB Output is correct
24 Correct 641 ms 17376 KB Output is correct
25 Correct 483 ms 17504 KB Output is correct
26 Correct 378 ms 17504 KB Output is correct
27 Correct 323 ms 17636 KB Output is correct
28 Correct 254 ms 18276 KB Output is correct
29 Correct 275 ms 19208 KB Output is correct
30 Correct 271 ms 20836 KB Output is correct
31 Correct 235 ms 21728 KB Output is correct
32 Correct 229 ms 22368 KB Output is correct