Submission #102610

#	Time	Username	Problem	Language	Result	Execution time	Memory
102610		popovicirobert	Race (IOI11_race)	C++14	100 / 100	753 ms	101088 KiB

race

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

using namespace std;

typedef vector <int> VI;
typedef vector < vector <int> > VVI;
typedef vector < vector < pair <int, int> > > VVPII;
typedef vector <ll> VLL;

struct Data {
    ll dst;
    int lvl;
    bool operator <(const Data &other) const {
        if(dst == other.dst) {
            return lvl < other.lvl;
        }
        return dst < other.dst;
    }
};

void dfs(int nod, int par, VVPII &g, int &ans, vector < multiset <Data> > &mst, VLL &Dst, VI &Lvl, int k) {
    for(auto it : g[nod]) {
        if(it.first != par) {
            Lvl[it.first] = Lvl[nod] + 1, Dst[it.first] = Dst[nod] + it.second;
            dfs(it.first, nod, g, ans, mst, Dst, Lvl, k);
            if(mst[nod].size() < mst[it.first].size()) {
                swap(mst[nod], mst[it.first]);
            }
        }
    }
    for(auto it : g[nod]) {
        if(it.first != par) {
            for(auto cur : mst[it.first]) {
                auto itr = mst[nod].lower_bound({k + 2LL * Dst[nod] - cur.dst, 0});
                if(itr != mst[nod].end() && itr -> dst + cur.dst - 2LL * Dst[nod] == k) {
                    ans = min(ans, itr -> lvl + cur.lvl - 2 * Lvl[nod]);
                }
            }
            for(auto cur : mst[it.first]) {
                mst[nod].insert(cur);
            }
        }
    }
    auto itr = mst[nod].lower_bound({k + Dst[nod], 0});
    if(itr != mst[nod].end() && itr -> dst - Dst[nod] == k) {
        ans = min(ans, itr -> lvl - Lvl[nod]);
    }
    mst[nod].insert({Dst[nod], Lvl[nod]});
}

int best_path(int n, int k, int H[][2], int L[]) {
    VVPII g(n + 1);
    for(int i = 0; i < n - 1; i++) {
        H[i][0]++, H[i][1]++;
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }
    vector < multiset <Data> > mst(n + 1);
    VLL dst(n + 1); VI lvl(n + 1);
    int ans = 2 * n;
    dfs(1, 0, g, ans, mst, dst, lvl, k);
    if(ans == 2 * n) {
        ans = -1;
    }
    return ans;
}

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