Submission #715996

#	Time	Username	Problem	Language	Result	Execution time	Memory
715996		ovidiush11	Race (IOI11_race)	C++14	100 / 100	461 ms	82748 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N_ = 2e5+1;

vector<vector<pair<int,int>>> a;
map<int,int> mp[N_];
int n,k,len[N_],sum[N_],ans = 1e9;

void dfs(int pos,int last,int ln,int sm)
{
    len[pos] = ln;
    sum[pos] = sm;
    mp[pos][sm] = ln;
    for(auto x : a[pos])
    {
        if(x.first == last)continue;
        dfs(x.first,pos,ln+1,sm+x.second);
    }
    return ;
}

void solve(int pos,int last)
{
    int K = k + 2 * sum[pos];
    for(auto v : a[pos])
    {
        if(v.first == last)continue;
        solve(v.first,pos);
        if(mp[v.first].size() > mp[pos].size())swap(mp[v.first],mp[pos]);
        for(auto i : mp[v.first])
        {
            if(mp[pos].find(K-i.first) != mp[pos].end()){
                ans = min(ans,mp[pos][K-i.first] + i.second - 2 * len[pos]);
            }
        }
        for(auto i : mp[v.first]){
            if(mp[pos].find(i.first) == mp[pos].end()){
                mp[pos].insert(i);
            }else{
                mp[pos][i.first] = min(mp[pos][i.first],i.second);
            }
        }
    }
}

int best_path(int n_, int k_, int h[][2], int l[])
{
    n = n_;k = k_;
    a.resize(n);
    for(int i = 0;i < n-1;i++)
    {
        int x = h[i][0],y = h[i][1];
        a[x].push_back({y,l[i]});
        a[y].push_back({x,l[i]});
    }
    dfs(0,-1,0,0);
    solve(0,-1);
    if(ans == 1e9)return -1;
    else return ans;
}

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