Submission #1256394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256394		mmmm2025	Race (IOI11_race)	C++20	0 / 100	7 ms	14400 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;
            dfs(u, v);
            dist[u] = dist[v] + w;
            depth[u] = depth[v] + 1;
            if(fixd[u].size() > fixd[v].size()){
                swap(fixd[u], fixd[v]);
            }
            for(auto [d, node]:fixd[u]){
                if(fixd[v][d] == 0 || depth[node] < depth[fixd[v][d]]){
                    fixd[v][d] = node;
                }               
                if(fixd[v][dk-d+dist[v]] != 0){
                        res = min(res, depth[node] + depth[fixd[v][dk-d+dist[v]]]-depth[v]);
                }
            }
            fixd[u].clear();
        }
    }
    ll best_path(int n,int k,int h[][2],int L[]){
        for(int i = 0; i < n-1; i++){
            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, 0);
        return res;
    }

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