Submission #1124014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124014		AverageAmogusEnjoyer	Race (IOI11_race)	C++20	100 / 100	470 ms	100568 KiB

race

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

int best_path(int n,int k,int ed[][2],int w[]) {
    vector<vector<pair<int,int>>> adj(n);
    for (int i=0;i<n-1;i++) {
        adj[ed[i][0]].emplace_back(ed[i][1],w[i]);
        adj[ed[i][1]].emplace_back(ed[i][0],w[i]);
    }
    vector<ll> depth(n);
    vector<int> depth2(n);
    auto dfs2=[&](auto &self,int u,int p)->void {
        for (auto &[v,w]: adj[u]) if (v!=p) {
            depth[v]=depth[u]+w;
            depth2[v]=depth2[u]+1;
            self(self,v,u);
        }
    };
    dfs2(dfs2,0,-1);
    vector<map<ll,int>> S(n);
    int ans=1<<30;
    auto dfs = [&](auto &self,int u,int p) -> void {
        S[u][depth[u]]=depth2[u];
        for (auto &[v,w]: adj[u]) if (v!=p) {
            self(self,v,u);
            if (S[v].size()>S[u].size()) swap(S[u],S[v]);
            // depth[a]+depth[b]-2*depth[u]=k
            // depth[b]=2*depth[u]+k-depth[a]
            for (auto &[other_depth,min_dep]: S[v]) {
                if (S[u].count(depth[u]*2+k-other_depth))
                    cmin(ans,S[u][depth[u]*2+k-other_depth]+min_dep-2*depth2[u]);
            }
            for (auto &[other_depth,min_dep]: S[v]) {
                if (S[u].count(other_depth)) 
                    cmin(S[u][other_depth],min_dep);
                else 
                    S[u][other_depth]=min_dep;
            }
        }
        // cout << "node " << u + 1 << endl;
        // for (auto &[other_dep,min_dep]: S[u]) {
            // cout << other_dep << " " << min_dep << endl;
        // }
    };
    dfs(dfs,0,-1);
    return (ans==1<<30?-1:ans);
}

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