Submission #1095415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095415		MtSaka	Race (IOI11_race)	C++17	100 / 100	272 ms	79208 KiB

race

#include"bits/stdc++.h"
#include "race.h"
#define overload(a,b,c,d,...) d
#define rep1(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep2(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}

int best_path(int n,int k,int h[][2],int l[]){
    vector<vector<pair<int,ll>>>g(n);
    rep(i,n-1){
        g[h[i][0]].eb(h[i][1],l[i]);
        g[h[i][1]].eb(h[i][0],l[i]);
    }
    vector<pair<ll,int>>dist(n,{1e9,1e9});
    {
        queue<int>que;
        que.emplace(0);
        dist[0]=pair<ll,int>{0,0};
        while(!que.empty()){
            int v=que.front();que.pop();
            for(auto [e,c]:g[v])if(dist[e].second==1e9){
                dist[e].first=dist[v].first+c;
                dist[e].second=dist[v].second+1;
                que.push(e);
            }
        }
    }
    vector<set<pair<int,ll>>>st(n);
    int ans=1e9;
    auto dfs=[&](auto&&dfs,ll v,ll p=-1)->void {
        st[v].emplace(dist[v]);
        for(auto [u,c]:g[v])if(u!=p){
            dfs(dfs,u,v);
            if(st[v].size()<st[u].size())swap(st[u],st[v]);
            for(auto [d1,d2]:st[u]){
                //d1+d-2*dist[v].first=k
                   auto it=st[v].lower_bound({2*dist[v].first+k-d1,-1});
                if(it!=st[v].end()&&it->first==2*dist[v].first+k-d1){
                    chmin(ans,it->second+d2-2*dist[v].second);
                }
            }
            for(auto [d1,d2]:st[u])st[v].emplace(d1,d2);
            st[u].clear();
        }
    };
    dfs(dfs,0);
    if(ans==1e9)ans=-1;
    return ans;
}

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