Submission #864386

#	Time	Username	Problem	Language	Result	Execution time	Memory
864386		nasir_bashirov	Race (IOI11_race)	C++11	0 / 100	2 ms	10332 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\

const int sz = 2e5 + 5;
vll g[sz];
ll n, k, h[sz], res = 1e9;
set<pll> st;
map<ll, multiset<ll>> mp;

void preCalc(ll node, ll par, ll c){
    h[node] = h[par] + 1;
    mp[c].insert(h[node]);
    for(pii i : g[node]){
        if(i.first == par)   continue;
        preCalc(i.first, node, c + i.second);
    }
}

void deletePath(ll node, ll par, ll c){
    mp[c].erase(mp[c].find(h[node]));
    for(pii i : g[node]){
        if(i.first == par) continue;
        deletePath(i.first, node, c + i.second);
    }
}

void insertPath(ll node, ll par, ll c){
    mp[c].insert(h[node]);
    for(pii i : g[node]){
        if(i.first == par) continue;
        insertPath(i.first, node, c + i.second);
    }
}

void dfs(ll node, ll par, ll c){
    if(c == k)  res = min(res, h[node]);
    st.insert({c, h[node]});
    if(c < k and mp[k - c].size())   res = min(res, h[node] + (*mp[k - c].begin()));
    if(c > k){
        auto it = st.lower_bound({c - k, 0});
        if(it != st.end())  res = min(res, h[node] - (*it).second);
    }
    st.insert({c, h[node]});
    for(pii i : g[node]){
        if(i.first == par) continue;
        if(node == 0)   st.clear();
        if(node == 0)   deletePath(i.first, node, c + i.second);
        dfs(i.first, node, c + i.second);
        if(node == 0)   insertPath(i.first, node, c + i.second);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N, k = K;
    for(int i = 0; i < n; i++){
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    h[0] = -1;
    preCalc(0, 0, 0);
    dfs(0, 0, 0);
    res = (res == 1e9 ? -1 : res);
    return res;
}

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