| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147859 | 2019-08-31T02:58:18 Z | imsifile | Trip to the Galapagos Islands (FXCUP4_island) | C++17 | 0 ms | 0 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 N_, int M, int K_, vector<int> F, vector<int> S, vector<int> E){
N=N_, K=K_;
memset(bcn, 0, sizeof(bcn)), mcn=vcn=pcn=ecn=0, memset(edg, 0, sizeof(edg));
for(int i=0; i<K; i++) con[i].clear(), wid[i].clear();
for(int i=0; i<505; i++) mat[i].clear();
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);
// ToDo
}
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;
}