Submission #1064647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064647		Hugo1729	Race (IOI11_race)	C++11	9 / 100	374 ms	41144 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;

vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={0};

ll k;

ll dfs_sizes(ll v, ll pV){
    sz[v]=0;
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            sz[v]+=dfs_sizes(w,v);
        }
    }
    return sz[v];
}

ll dfs_centroid(ll v, ll pV, ll subtree_sz){
    for(auto [w,d] : adj[v]){
        if(pV!=v&&!marked[v]&&sz[v]>=(subtree_sz/2)){
            return dfs_centroid(w,v,subtree_sz);
        }
    }
    return v;
}

void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            if(dist+d<=1000000){
                a.push_back({dist+d,l+1});
                dfs_paths(w,v,dist+d,l+1,a);
            }
        }
    }
}


ll centroid_decomposition(ll v){
    ll c = dfs_centroid(v,v,dfs_sizes(v,v));


    marked[c]=1;
    
    ll ans=1000001;
    map<ll,ll> m;
    m[0]=0;

    for(auto [w,d] : adj[c]){
        if(!marked[w]){
            vector<pair<ll,ll>> a;
            dfs_paths(w,c,d,1,a);

            for(auto [dist,l] : a){
                if(m.count(k-dist)){
                    ans=min(ans,l+m[k-dist]);
                }
            }
            for(auto [dist,l] : a){
                if(m.count(dist))m[dist]=min(m[dist],l);
                else m[dist]=l;
            }



            ans = min(ans,centroid_decomposition(w));
        }
    }

    return ans;
}




int best_path(int N, int K, int H[][2], int L[]){
    for(ll i=0;i<N-1;i++){
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }

    k=K;
    ll ans = centroid_decomposition(0);

    return (ans==1000001?-1:ans);
}

Compilation message (stderr)

race.cpp: In function 'll dfs_sizes(ll, ll)':
race.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'll dfs_centroid(ll, ll, ll)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'void dfs_paths(ll, ll, ll, ll, std::vector<std::pair<long long int, long long int> >&)':
race.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'll centroid_decomposition(ll)':
race.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for(auto [w,d] : adj[c]){
      |              ^
race.cpp:58:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |             for(auto [dist,l] : a){
      |                      ^
race.cpp:63:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |             for(auto [dist,l] : a){
      |                      ^

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