Submission #307468

#	Time	Username	Problem	Language	Result	Execution time	Memory
307468		juggernaut	Race (IOI11_race)	C++14	21 / 100	3072 ms	14624 KiB

race

#include"race.h"
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
int k,inf=2e9,ans=inf,t,res[1000005],mt[1000005],a[200005];
bool vis[200005];
vector<pair<int,int>>g[200005];
void app(int v,int p,int len,int depth){
    if(k>len&&mt[k-len]==t)ans=min(ans,depth+res[k-len]);
    else if(k==len)ans=min(ans,depth);
    if(len>k)return;
    for(auto to:g[v])
        if(to.fr!=p&&!vis[to.fr])app(to.fr,v,len+to.sc,depth+1);
}
void update(int v,int p,int len,int depth){
    if(k>len&&mt[len]!=t){
        mt[len]=t;
        res[len]=depth;
    }else if(k>len)res[len]=min(depth,res[len]);
    else return;
    for(auto to:g[v])
        if(to.fr!=p&&!vis[to.fr])update(to.fr,v,len+to.sc,depth+1);
}
int dfs(int v,int p){
    a[v]=1;
    for(auto to:g[v])
        if(to.fr!=p&&!vis[to.fr])
            a[v]+=dfs(to.fr,v);
    return a[v];
}
int centroid(int v){
    dfs(v,v);
    bool flag=true;
    int p=v;
    while(flag){
        flag=false;
        for(auto to:g[v]){
            if(to.fr!=p&&!vis[to.fr]&&(a[to.fr]<<1)>=a[v]){
                p=v;
                v=to.fr;
                flag=true;
                break;
            }
        }
    }
    return v;
}
void go(int v){
    v=centroid(v);
    vis[v]=1;
    t++;
    for(auto to:g[v])
        if(!vis[to.fr]){
            app(to.fr,v,to.sc,1);
            update(to.fr,v,to.sc,1);
        }
    for(auto to:g[v])
        if(!vis[to.fr])go(to.fr);
}
int best_path(int N,int K,int H[][2],int L[]){
    k=K;
    for(int i=0;i+1<N;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }
    go(0);
    if(ans==inf)return -1;
    return ans;
}

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