Submission #807449

#	Time	Username	Problem	Language	Result	Execution time	Memory
807449		annabeth9680	Race (IOI11_race)	C++17	100 / 100	440 ms	107588 KiB

race

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5+5;
vector<pair<ll,ll>> adj[MAXN]; //first second node, then weight of the edge
map<ll,ll> mindist[MAXN];
ll dep[MAXN],weight[MAXN];
int K; ll ans = 1e18;
void dfs(int u, int p){
    for(auto x : adj[u]){
        if(p != x.first){
            dep[x.first] = dep[u]+1;
            weight[x.first] = weight[u]+x.second;
            mindist[x.first][weight[x.first]] = dep[x.first];
            //cout << x.first << " " << dep[x.first] << " " << weight[x.first] << " " << "\n";
            dfs(x.first,u);
        }
    }
}
void smalltolarge(int u, int p){
    ll F = K+2*weight[u];
    for(auto x : adj[u]){
        if(x.first != p){
            int v = x.first;
            smalltolarge(v,u);
            if(mindist[v].size() > mindist[u].size()){
                swap(mindist[v],mindist[u]);
            }
            //cout << u << " " << v << "\n";
            for(auto m : mindist[v]){
                if(mindist[u].find(F-m.first) != mindist[u].end()){
                    ans = min(ans,mindist[u][F-m.first]+m.second-2*dep[u]);
                }
            }
            for(auto m : mindist[v]){
                if(mindist[u].find(m.first) == mindist[u].end()){
                    mindist[u][m.first] = m.second;
                }
                else{
                    mindist[u][m.first] = min(mindist[u][m.first],m.second);
                }
                //cout << m.first << " " << mindist[u][m.first] << " ";
            }
        }
    }
}
int best_path(int n, int k, int h[][2], int length[]){
    K = k;
    for(int i = 0;i<n-1;++i){
        int u = h[i][0], v = h[i][1];
        adj[u].push_back({v,length[i]});
        adj[v].push_back({u,length[i]});
    }
    mindist[0][0] = 0;
    dfs(0,-1);
    smalltolarge(0,-1);
    if(ans != 1e18) return ans;
    else return -1;
}

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