Submission #197495

#	Time	Username	Problem	Language	Result	Execution time	Memory
197495		handlename	Race (IOI11_race)	C++17	100 / 100	713 ms	36428 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define mp make_pair
#define pb push_back
int n,k,res;
vector<pair<int,int> > adj[200001];
int sub[200001],lvl[200001],par[200001];
int ans[1000001];
stack<int> st;
int dfs1(int u,int p,int l){
    sub[u]=1;
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        if (i.first==p) continue;
        sub[u]+=dfs1(i.first,u,l);
    }
    return sub[u];
}
int dfs2(int u,int p,int sn){
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        if (i.first==p) continue;
        if (sub[i.first]>sn/2){
            return dfs2(i.first,u,sn);
        }
    }
    return u;
}
vector<pair<int,int> > branch;
void dfs3(int u,int p,long long dist,int edges){
    //cout<<dist<<" "<<edges<<'\n';
    if (dist>k){
        return;
    }
    branch.pb(mp(dist,edges));
    st.push(dist);
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        if (i.first==p) continue;
        dfs3(i.first,u,dist+i.second,edges+1);
        if (p==-1){
            branch.pb(mp(dist,edges));
            for (auto j:branch){
                res=min(res,ans[k-j.first]+j.second);
            }
            for (auto j:branch){
                ans[j.first]=min(ans[j.first],j.second);
            }
            branch.clear();
        }
    }
}
// Building from node u, with a parent p and level l
void build(int u,int p,int l){
    int cn=dfs1(u,p,l);
    int cent=dfs2(u,p,cn);
    if (p==-1) p=cent;
    par[cent]=p;
    lvl[cent]=l;
    //cout<<"centroid: "<<cent<<'\n';
    dfs3(cent,-1,0,0);
    while (!st.empty()){
        int cur=st.top();
        ans[cur]=1e9;
        st.pop();
    }
    for (auto i:adj[cent]){
        if (lvl[i.first]!=-1) continue;
        build(i.first,cent,l+1);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    n=N;
    k=K;
    for (int i=0;i<n-1;i++){
        adj[H[i][0]].pb(mp(H[i][1],L[i]));
        adj[H[i][1]].pb(mp(H[i][0],L[i]));
    }
    res=1e9;
    for (int i=0;i<=k;i++) ans[i]=1e9;
    memset(lvl,-1,sizeof(lvl));
    build(0,-1,0);
    if (res==1e9) return -1;
    return res;
}

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