Submission #1144061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144061		pedreitorzelda	Race (IOI11_race)	C++20	0 / 100	0 ms	320 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<bool>vis;
vector<map<ll,ll>>nodes;
vector<vector<pair<ll,ll>>>g;
vector<ll>dist_way;
vector<ll>dist_cant;
ll n,k;
ll cur_ans = int(1e9);


void dfs(ll u){
    if(vis[u])return;
    vis[u]=true;
    for(auto it : g[u]){
        if(!vis[it.first]){
            dfs(it.first);
            ll son = it.first;
            if(nodes[son].size()>nodes[u].size()){
                swap(nodes[u],nodes[son]);
            }
            for(auto it2 : nodes[son]){
                //cout << u << " - " << son<<" :"<< k+2*dist_way[u]-it2.first << " " << k << " " << dist_way[u] << " " << it2.first << endl;
                if(nodes[u].find(k+2*dist_way[u]-it2.first)!=nodes[u].end()){
                    cur_ans = min(cur_ans, nodes[u][k+2*dist_way[u]-it2.first]+it2.second-2*dist_cant[u]);
                }
            }
            for(auto it2 : nodes[son]){
                if(nodes[u].find(it2.first)==nodes[u].end())nodes[u][it2.first]=it2.second;
                else nodes[u][it2.first] = min(nodes[u][it2.first],it2.second);
            }
        }
    }
    return;
}
void prep_dfs(int u){
    if(vis[u])return;
    vis[u]=true;
    nodes[u][dist_way[u]]=dist_cant[u];
    for(auto it : g[u]){
        if(!vis[it.first]){
            dist_way[it.first]=dist_way[u]+it.second;
            dist_cant[it.first]=dist_cant[u]+1;
            prep_dfs(it.first);
        }
    }return;
}
int best_path(int N, int K,int H[][2], int L[]){
    if(k==1){return 0;}
    nodes.resize(N+2);
    vis.resize(N+2,0);
    g.resize(N+2);
    dist_way.resize(N+2,0);
    dist_cant.resize(N+2,0);
    n=N,k=K;
    cur_ans = -1;
    for(ll i=0;i<N-1;i++){
        g[H[i][0]].push_back({H[i][1],L[i]});
        g[H[i][1]].push_back({H[i][0],L[i]});
    }
    prep_dfs(0);
    for(int i=0;i<=n;i++)vis[i]=0;
    dfs(0);

    nodes.clear();
    vis.clear();
    g.clear();
    dist_way.clear();
    dist_cant.clear();
    if(cur_ans==1e9)cur_ans = -1;
    return cur_ans;
}
/*

signed main(){
    ll t;
    cin >> t;
    while(t--){

        int n,k;
        cin >> n >> k;
        int H[n][2];
        int L[n];
        for(int i=0;i<n-1;i++){
            for(int j=0;j<2;j++){
                cin >> H[i][j];
            }
        }
        for(int i=0;i<n-1;i++)cin >> L[i];
        cout << best_path(n,k,H,L) << endl;
    }
    return 0;
}
*/

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