Submission #497659

#	Time	Username	Problem	Language	Result	Execution time	Memory
497659		Deepesson	경주 (Race) (IOI11_race)	C++17	43 / 100	3017 ms	41088 KiB

race

#include <bits/stdc++.h>
#define MAX 205000
bool existe[MAX];
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
int dfs(int pos,int prev){
    int size=1;
    for(auto&y:con[pos]){
        auto x = y.first;
        if(x==prev||existe[x])continue;
        size+=dfs(x,pos);
    }
    return size;
}
int centroide=0;
int find(int pos,int prev,int sz){
    int size=1;
    int max=0;
    for(auto&y:con[pos]){
        auto x = y.first;
        if(x==prev||existe[x])continue;
        int b = find(x,pos,sz);
        max=std::max(max,b);
        size+=b;
    }
    max=std::max(max,sz-size);
    if(max<=sz/2)centroide=pos;
    return size;
}
int Quer;
int best=1e9;
std::unordered_map<int,int> tabela;
void explorar(int pos,int prev,int dist1=0,int dist2=0){
    if(dist1>Quer)return;
    if(dist1==Quer){
        best=std::min(best,dist2);
    }
    if(dist1<Quer){
        int falta = Quer-dist1;
        auto it = tabela.find(falta);
        if(it!=tabela.end()){
            best=std::min(best,it->second+dist2);
        }
    }
    for(auto&x:con[pos]){
        if(x.first==prev||existe[x.first])continue;
        explorar(x.first,pos,dist1+x.second,dist2+1);
    }
}
void computar(int pos,int prev,int dist1=0,int dist2=0){
    if(dist1>Quer)return;
    if(dist1<Quer){
        auto it = tabela.find(dist1);
        if(it==tabela.end()){
            tabela[dist1]=dist2;
        }else it->second=std::min(it->second,dist2);
    }
    for(auto&x:con[pos]){
        if(x.first==prev||existe[x.first])continue;
        computar(x.first,pos,dist1+x.second,dist2+1);
    }
}
void Decompor(int x){
    int tam = dfs(x,-1);
    find(x,-1,tam);
    int c = centroide;
    existe[c]=true;
    for(auto&x:con[c]){
        if(existe[x.first])continue;
        explorar(x.first,-1,x.second,1);
        computar(x.first,-1,x.second,1);
    }
    tabela.clear();
    for(auto&y:con[c]){
        auto x = y.first;
        if(existe[x])continue;
        Decompor(x);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    for(int i=0;i!=N-1;++i){
        int a = H[i][0],b=H[i][1],c=L[i];
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    Quer=K;
    best=1e9;
    Decompor(0);
    if(best>1e6)return -1;
    return best;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57