Submission #1147951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147951		Kodik	Race (IOI11_race)	C++20	0 / 100	7 ms	14400 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ss second
#define ff first
typedef long long ll;
#define ll ll
using pi = array<ll, 2>;
const ll MOD = 1e9+7;

ll n, k;
const ll maxn = 2e5;
vector<pair<ll,ll>> g[maxn];
ll sz[maxn];
pi node[maxn];
map<ll,ll> len_to_dep[maxn];

void dfs_sz(ll v, ll p, ll d, ll l){
    sz[v] = 1;
    node[v] = {l, d};
    for(auto &[w,u] : g[v]){
        if(u!=p){
            dfs_sz(u, v, d+1, l+w);
            sz[v] += sz[u];
        }
    }
}

ll ans = 1e9;


void dfs(ll v, ll p){
    ll mx = -1, bigChild = -1;
    for(auto& [w, u] : g[v]){
        if(u!=p&&sz[u]>mx){
            mx = sz[u];
            bigChild = u;
        }
        if(u!=p){
            dfs(u, v);
        }
    }
    if(bigChild!=-1){
        swap(len_to_dep[v], len_to_dep[bigChild]);
    }
    if(len_to_dep[v].count(node[v][0])>0) len_to_dep[v][node[v][0]] = min(len_to_dep[v][node[v][0]], node[v][1]);
    else len_to_dep[v][node[v][0]] = node[v][1];
    for(auto &[w, u] : g[v]){
        if(u!=p&&u!=bigChild){
            for(auto &[l, d] : len_to_dep[u]){
                ll seek = k-l+node[v][0];
                if(len_to_dep[v].count(seek)>0){
                    ans = min(ans, d+len_to_dep[v][seek]-2*node[v][1]);
                }
            }
            for(auto &[l, d] : len_to_dep[u]){
                if(len_to_dep[v].count(l)>0) len_to_dep[v][l] = min(len_to_dep[v][l], d);
                else len_to_dep[v][l] = d;
            }
        }
    }
    if(len_to_dep[v].count(k)>0) ans = min(ans, len_to_dep[v][k]);
}

int best_path(int na, int ka, int h[][2], int l[]){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    n = na, k = ka; 
    for(ll i = 0; i < n-1; ++i){
        ll x; cin >> x;
        g[h[i][0]].push_back({x, h[i][1]});
        g[h[i][1]].push_back({x, h[i][0]});
    }
    dfs_sz(0,-1,0,0);
    dfs(0,-1);
    if(ans==1e9) ans = -1;
    cout << ans << '\n';
    return 0;
}

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