Submission #1256591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256591		mmmm2025	Race (IOI11_race)	C++20	43 / 100	246 ms	82364 KiB

race

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    vector<array<ll, 2>> adj[200001];
    map<ll, ll> fixd[200001];
    ll dist[200001];
    ll depth[200001];
    ll dk = 0;
    ll res = 1e11*2+1;
    void dfs( ll v, ll pre){
        fixd[v][dist[v]] = v;
        for(auto x:adj[v]){
            ll u = x[0];
            ll w = x[1];
            if(u == pre)continue;
            dist[u] = dist[v] + w;
            depth[u] = depth[v] + 1;
            dfs(u, v);
            if(fixd[u].size() > fixd[v].size()){
                swap(fixd[u], fixd[v]);
            }
            for(auto [d, node]:fixd[u]){
                if(node == 0)continue;
                 if(fixd[v].find(dk-d+2*dist[v]) != fixd[v].end()){
                    res = min(res, depth[node] + depth[fixd[v][dk-d+2*dist[v]]]-2*depth[v]);
                }
                if(fixd[v].find(d) == fixd[v].end() || depth[node] < depth[fixd[v][d]]){
                    fixd[v][d] = node;
                }               
            }
            fixd[u].clear();
        }
    }
    ll best_path(int n,int k,int h[][2],int L[]){
        for(int i = 0; i < n-1; i++){
            h[i][0]++; 
            h[i][1]++; 
            adj[h[i][0]].push_back({h[i][1], L[i]});
            adj[h[i][1]].push_back({h[i][0], L[i]});
        }
        dk = k;
        res = 1e12;
        for(int i = 0; i <= n; i++){
            dist[i] = 0;
            depth[i] = 0;
            fixd[i].clear();
        }
        dfs(1, -1);
        if(res == 1e12)return -1;
        else return res;
    }
   /*
int main(){
    int n,k;
    cin >> n >> k;
    int h[n-1][2];
    int L[n-1];
    for(int i = 0; i < n-1; i++){
        cin >> h[i][0] >> h[i][1] ;
    }
    for(int i = 0;i < n-1;i++)cin >> L[i];
    cout << best_path(n,k,h,L) << endl;
}
    */

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