제출 #524272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524272		Deepesson	자매 도시 (APIO20_swap)	C++17	0 / 100	880 ms	524292 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#define MAX 305000
int n,m;
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
std::vector<pip> tmp;
std::vector<pii> con[MAX];
int pai[MAX];
bool acabou[MAX];
std::vector<int> candidatos[MAX];
int conexoes[MAX];
int fins[MAX];

int up[MAX][25];
int ph[MAX][25];
int prof[MAX];
void dfs(int pos,int prev,int peso,int depth){
    prof[pos]=depth;
    up[pos][0]=prev;
    ph[pos][0]=peso;
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        dfs(x.first,pos,x.second,depth+1);
    }
}
int find(int a){
    if(pai[a]==a)
        return a;
    return pai[a]=find(pai[a]);
}
int peso=0;
void Union(int a,int b){
    conexoes[a]++;
    conexoes[b]++;
    a=find(a);
    b=find(b);
    if(a==b)acabou[a]=true;
    else {
        con[a].push_back({b,peso});
        con[b].push_back({a,peso});
        pai[b]=a;
        for(auto&x:candidatos[b]){
            candidatos[a].push_back(x);
        }
        candidatos[b].clear();
        acabou[a]=std::max(acabou[a],acabou[b]);
    }
    if(acabou[a]){
        for(auto&x:candidatos[a])fins[x]=peso;
        candidatos[a].clear();
        return;
    }
    int count=0;
    {
        std::vector<int> novo;
        for(auto&x:candidatos[a]){
            if(conexoes[x]==1)++count;
        }
    }
    if(count>2){
        for(auto&x:candidatos[a]){
            fins[x]=peso;
        }
        candidatos[a].clear();
    }
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n=N;
    m=M;

    for(int i=0;i!=M;++i){
        tmp.push_back({W[i],{U[i],V[i]}});
    }

    std::sort(tmp.begin(),tmp.end());

    for(auto&x:fins)x=1e9;

    for(int i=0;i!=N;++i){
        pai[i]=i;
        candidatos[i].push_back(i);
    }

    for(auto&x:tmp){
        peso=x.first;
        int u = x.second.first,v=x.second.second;
        Union(u,v);
    }

    dfs(0,-1,-1,0);

    for(int j=1;j!=25;++j){
        for(int i=0;i!=N;++i){
            if(up[i][j-1]==-1){
                up[i][j]=-1;
                continue;
            }
            up[i][j]=up[up[i][j-1]][j-1];
            ph[i][j]=std::max(ph[up[i][j-1]][j-1],ph[i][j-1]);
        }
    }
   /* for(int i=0;i!=N;++i){
        std::cout<<fins[i]<<" ";
    }
    std::cout<<"\n";*/
}

int lcaval(int x,int y){
    if(prof[y]<prof[x])std::swap(x,y);
    int ans=0;
    for(int i=24;i!=-1;--i){
        int prox = up[y][i];
        if(prox==-1)continue;
        if(prof[prox]>=prof[x]){
            ans=std::max(ans,ph[y][i]);
            y=prox;
        }
    }
    assert(prof[x]==prof[y]);
   /// std::cout<<x<<" "<<y<<"preprof\n";
    for(int i=24;i!=-1;--i){
        int a = up[y][i];
        int b = up[x][i];
        if(a==-1||b==-1)continue;
        if(a!=b){
            ans=std::max(ans,ph[y][i]);
            ans=std::max(ans,ph[x][i]);
            x=b;
            y=a;
        }
    }
  ///  std::cout<<x<<" "<<y<<"<-\n";
    if(x!=y){
        ans=std::max(ans,ph[y][0]);
        ans=std::max(ans,ph[x][0]);
        x=up[x][0];
        y=up[y][0];
    }
    ///assert(x==y);
  ///  std::cout<<"Retorna "<<ans<<"\n";
  ///  std::cout<<x<<" "<<y<<"\n";
    return ans;
}

int getMinimumFuelCapacity(int X, int Y) {
  if(fins[X]==1e9&&fins[Y]==1e9)return -1;
  ///Proxima etapa: Achar o peso minimo entre o caminho de X e Y, a resposta sera max(min(fins[X],fins[Y]),caminho)
  int ans = std::min(fins[X],fins[Y]);
  return std::max(ans,lcaval(X,Y));
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27