Submission #395970

#	Time	Username	Problem	Language	Result	Execution time	Memory
395970		Jarif_Rahman	Race (IOI11_race)	C++17	0 / 100	10 ms	14412 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
const int lim = 2e5+1;
 
ll k;
set<pair<ll, int>> s[lim];
vector<pair<int, ll>> v[lim];
ll ans = 1e18;
 
void dfs(int nd, int ss, ll dis, int depth){
    for(auto [x, w]: v[nd]) if(x != ss) dfs(x, nd, dis+w, depth+1);
    int mx = s[nd].size(), in = -1;
    for(auto [x, w]: v[nd]) if(x != ss){
        if((int)s[x].size() > mx){
            mx = (int)s[x].size();
            in = x;
        }
    }
    if(in != -1) swap(s[nd], s[in]);
    for(auto [x, w]: v[nd]) if(x != ss){
        for(auto [d, dpt]: s[x]){
            dpt-=depth;
            d-=dis;
            ll dd = k-d;
            if(dd == 0){
                ans = min(ans, (ll)dpt);
            }
            else{
                auto it = s[nd].lower_bound(make_pair(dd+dis, 0));
                if(it != s[nd].end() && it->f == dd+dis){
                    ans = min(ans, dpt+(ll)(it->sc)-depth);
                }
            }
        }
        while(!s[x].empty()){
        	s[nd].insert(*s[x].begin());
        	s[x].erase(s[x].begin());
        }
    }
    s[nd].insert({dis, depth});
}
 
int best_path(int n, int k, int edges[][2], int w[]){
    ::k = k;
    for(int i = 0; i < n-1; i++){
        v[edges[i][0]].pb({edges[i][1], w[i]});
        v[edges[i][1]].pb({edges[i][0], w[i]});
    }
    dfs(0, -1, 0LL, 0);
    if(ans == inf) ans = -1;
    return ans;
}

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