Submission #95918

#	Time	Username	Problem	Language	Result	Execution time	Memory
95918		mayhoubsaleh	Race (IOI11_race)	C++14	21 / 100	150 ms	17784 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back

using namespace std;
int n,k,inf=1e7,ans=inf,sz[200005],cnt[1000006];bool vis[200005];
vector<pair<int,int>>v[100005],part;//part: first=dist,second=highways
vector<int>all;
void dfssz(int nod,int par){
    sz[nod]=1;
    for(auto i:v[nod]){
        int u=i.first;
        if(vis[u]||u==par)continue;
        dfssz(u,nod);
        sz[nod]+=sz[u];
    }
}

int getcn(int nod,int par,int tot){
    for(auto i:v[nod]){
        int u=i.first;
        if(u==par||vis[u])continue;
        if(sz[u]>tot/2)return getcn(u,nod,tot);
    }
    return nod;
}

void dfs(int nod,int par,int d,int hw){
    if(d>k)return;
    part.pb({d,hw});
    all.pb(d);
    ans=min(ans,cnt[k-d]+hw);
    for(auto i:v[nod]){
        if(vis[i.first]||i.first==par)continue;
        dfs(i.first,nod,d+i.second,hw+1);
    }
}
void solve(int cn){
    all.clear();
    for(auto i:v[cn]){
        int u=i.first;
        if(vis[u])continue;
        part.clear();
        dfs(u,cn,i.second,1);
        for(auto j:part){
            cnt[j.first]=min(cnt[j.first],j.second);
        }
    }
    for(auto i:all){
        cnt[i]=inf;
    }

}
void dec(int rot){
    dfssz(rot,0);
    int cn=getcn(rot,0,sz[rot]);
    cnt[0]=0;
    solve(cn);
    vis[cn]=1;
    for(auto i:v[cn]){
        int u=i.first;
        if(vis[u])continue;
        dec(u);
    }

}
int best_path(int N, int K, int H[][2], int L[])
{
  n=N,k=K;
    for(int i=0;i<n-1;i++){
        int a=H[i][0],b=H[i][1],c=L[i];
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=0;i<=k;i++){
        cnt[i]=inf;
    }
    dec(1);
    if(ans==inf)return -1;
    return ans;
}
/*int N,K,L[200006],H[200006][2];
int main(){
    cin>>N>>K;
    for(int i=0;i<N-1;i++){
        cin>>H[i][0]>>H[i][1]>>L[i];
    }
    int sol;
    cin>>sol;
    int x=best_path(N,K,H,L);
    if(x==sol)cout<<"Correct"<<endl;
    return 0;
}
*/

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