Submission #838803

#	Time	Username	Problem	Language	Result	Execution time	Memory
838803		imarn	Race (IOI11_race)	C++14	100 / 100	406 ms	97428 KiB

race

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
ll k;
int ans=1e7;
vector<pii>g[N];
unordered_map<ll,int>d[N];
void dfs(int u=0,int p=0,int lca=0,ll cur=0){
    d[u][cur]=lca;
    for(auto v:g[u]){
        if(v.f==p)continue;
        dfs(v.f,u,lca+1,cur+v.s);
        if(d[u].size()<d[v.f].size())swap(d[u],d[v.f]);
        for(auto it : d[v.f]){
            if(d[u].find(k-it.f+2*cur)!=d[u].end()){
                ans=min(ans,it.s+d[u][k-it.f+2*cur]-2*lca);
            }
        }
        for(auto it : d[v.f]){
            if(d[u].find(it.f)==d[u].end())d[u][it.f]=it.s;
            else d[u][it.f]=min(d[u][it.f],it.s);
        }
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<N-1;i++){
        g[H[i][0]].pb({H[i][1],L[i]});
        g[H[i][1]].pb({H[i][0],L[i]});
    }dfs();
    return (ans==1e7?-1:ans);
}

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