Submission #771070

#	Time	Username	Problem	Language	Result	Execution time	Memory
771070		kirakaminski968	Race (IOI11_race)	C++17	0 / 100	7 ms	14420 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 nodes, then weight
ll depth[MAXN],weightsum[MAXN],ans;
int n,k;
map<ll,ll> help[MAXN];
void dfs(int u, int p, ll d, int dep){
    depth[u] = dep;
    weightsum[u] = d;
    help[u][d] = dep;
    for(auto v : adj[u]){
        if(v.first != p){
            dfs(v.first,u,d+v.second,dep+1);
        }
    }
}
void smalltolarge(int u, int p){
    ll tar = k+weightsum[u]*2;
    for(auto v : adj[u]){
        if(v.first != p){
            smalltolarge(v.first,u);
            if(help[v.first].size() > help[u].size()) swap(help[v.first],help[u]);
            for(auto x : help[v.first]){
                if(help[u].find(tar-x.first) != help[u].end()){
                    ans = min(ans,x.second+help[u][tar-x.first]-2*depth[u]);
                }
            }
            for(auto x : help[v.first]){
                if(help[u].find(x.first) == help[u].end()){
                    help[u].insert(x);
                }
                else{
                    help[u][x.first] = min(help[u][x.first],x.second);
                }
            }
        }
    }
}
int best_path(int N, int K, int edges[][2], int lengths[]){
    if(K == 1) return 0;
    n = N; k = K; ans = INT_MAX;
    for(int i = 0;i<N-1;i++){
        adj[edges[i][0]].push_back({edges[i][1],lengths[i]});
        adj[edges[i][1]].push_back({edges[i][0],lengths[i]});
    }
    dfs(0,-1,0,0);
    smalltolarge(0,-1);
    return ans;
}

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