Submission #307560

#	Time	Username	Problem	Language	Result	Execution time	Memory
307560		amunduzbaev	Race (IOI11_race)	C++14	0 / 100	4 ms	4992 KiB

race

#include "race.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> m, v[200005];
int g[200005],used[200005],n,k;
map<int ,int>len;

void dfs(int vi,int p){
    g[vi]++;
    for(int i=0;i<v[vi].size();i++){
        int b=v[vi][i].first;
        if(used[b]||b==p)continue;
        dfs(b,vi);
        g[vi]+=g[b];
    }

}
int centr(int u,int p,int s){
    for(auto x:v[u]){
        int b=x.first;
        if(used[b]||p==b)
            continue;
        if(g[b]>s/2)
            return centr(b,u,s);
    }
    return u;
}
void dfs1(int vi,int p,int d,int t){
    if(d>k)
        return ;
    m.push_back({d,t});
    for(auto x:v[vi]){
        int b=x.first;
        int c=x.second;
        if(used[b]||p) continue;
        dfs1(b,vi,c+d,t+1);
    }
}
void dfs2(int vi,int p,int d,int t){
    if(d>k)
        return ;

    if(!len.count(d))
        len[d]=t;

    else
        len[d]=min(t,len[d]);

    m.push_back({d,t});
    for(auto x:v[vi]){
        int b=x.first;
        int c=x.second;
        if(used[b]||p) continue;
        dfs2(b,vi,c+d,t+1);
    }
}
int fans(int u,int p){
    int ans=INT_MAX;
    len.clear();
    dfs(u,u);
    //cout<<"works\n";
    u=centr(u,u,g[u]);
    len[0]=0;
    used[u]=1;
    //cout<<"works\n";
    for(auto x:v[u]){
        m.clear();
        int b=x.first,c=x.second;
        if(used[b]) continue;
        dfs1(b,u,c,1);
        for(auto x:m){
            int d=x.first;
            int t=x.second;;
            if(len.count(k-d)){
                ans=min(ans,len[k-d]+t);
            }//cout<<d<<" "<<t<<"\n";
        }
        dfs2(b,u,c,1);
    }
    for( auto x : v[u]){
        int b=x.first;
        if(used[b]||p==b) continue;
        ans=min(ans,fans(b,u));
    }
    return ans;
}
int best_path(int N, int K, int h[][2], int l[]){
    n=N,k=K;
    if(k==0)
        return 0;
    for(int i=0;i<n-1;i++){
        v[h[i][0]].push_back({h[i][1],l[i]});
        v[h[i][1]].push_back({h[i][0],l[i]});
    }

    int ans=fans(0,-1);
    ans=(ans==INT_MAX ? -1:ans);
    //cout<<ans<<" ";
    return ans;
}

/*

4 3
0 1 1
1 2 2
1 3 4
2

*/

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<v[vi].size();i++){
      |                 ~^~~~~~~~~~~~~

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