Submission #864948

#	Time	Username	Problem	Language	Result	Execution time	Memory
864948		nasir_bashirov	Race (IOI11_race)	C++11	0 / 100	3 ms	14940 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;
vl v[sz];
 
set<pll> dfs(ll node, ll par, ll w){
    h[node] = h[par] + 1;
    set<pll> st;
    for(pll i : g[node]){
        if(i.first == par)  continue;
        set<pll> temp = dfs(i.first, node, i.second);
        if(temp.size() > st.size()) swap(st, temp);
        for(pll j : temp){
            auto it = st.lower_bound({k - j.first, 0});
            if(it != st.end() and j.first + (*it).first == k)  res = min(res, j.second + (*it).second - 2 * h[node]);
        }
        for(pll j : temp){
            if(j.first == k)    res = min(res, j.second - h[node]);
            st.insert(j);
        }
    }
    set<pll> fnl;
    for(pll i : st){
        fnl.insert({i.first + w, i.second});
    }   
    fnl.insert({w, h[node]});
    return fnl;
}
 
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;
    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