Submission #553067

#	Time	Username	Problem	Language	Result	Execution time	Memory
553067		RaresFelix	Race (IOI11_race)	C++17	100 / 100	1006 ms	53300 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define MN 200071
#define MK 20
using namespace std;
using ll = long long;
vector<pair<int, int> > L[MN];

namespace LCA {
    static inline int log2(const int &v) {
        return 31 - __builtin_clz(v);
    }
    int In[MN], Out[MN], tmr;
    ll Niv[MN], RMQ[MK][MN * 2];
    void dfi(int u, int p, int niv) {
        In[u] = Out[u] = ++tmr;
        RMQ[0][In[u]] = Niv[u] = niv;
        for(auto [it, w] : L[u]) if(it != p) {
            dfi(it, u, niv + w);
            RMQ[0][Out[u] = ++tmr] = Niv[u];
        }
    }
    void init(int n) {
        for(int k = 1; k < MK; ++k)
            for(int i = 1; i <= n; ++i)
                RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1 << (k-1))]);
    }
    int query(int st, int dr) {
        int l = log2(dr - st + 1);
        return min(RMQ[l][st], RMQ[l][dr - (1 << l) + 1]);
    }
    int dist(int u, int v) {
        return Niv[u] + Niv[v] - 2 * query(min(In[u], In[v]), max(Out[u], Out[v]));
    }
}

bool Used[MN];
int Sz[MN];

void dfi(int u, int p) {
    Sz[u] = 1;
    for(auto &[it, w] : L[u])
        if(it != p && !Used[it]) dfi(it, u), Sz[u] += Sz[it];
}

int centr(int u, int p, const int &sz) {
    for(auto [it, w] : L[u])
        if(it != p && !Used[it] && Sz[it] * 2 > sz) return centr(it, u, sz);
    return u;
}

void dfc(int u, int p, vector<tuple<int, ll, int> > &comp, ll d, int niv = 1) {
    comp.push_back({u, d, niv});
    for(auto [it, w] : L[u])
        if(it != p && !Used[it])
            dfc(it, u, comp, d + w, niv + 1);
}

void desc(int u, int par_comp, int k, int &rez) {
    dfi(u, 0);
    int c = centr(u, 0, Sz[u]);
    map<ll, int> Posib;
    Used[c] = 1;
    Posib[0] = 0;
    for(auto [it, w] : L[c]) {
        if(Used[it]) continue;
        vector<tuple<int, ll, int> > comp;
        dfc(it, c, comp, w);
        for(auto &[u, dist, niv] : comp)
            if(Posib.count(k - dist)) rez = min(rez, niv + Posib[k - dist]);
        for(auto &[u, dist, niv] : comp)
            if(!Posib.count(dist)) Posib[dist] = niv;
            else Posib[dist] = min(Posib[dist], niv);
    }
    for(auto &[it, w] : L[c])
        if(!Used[it])
            desc(it, c, k, rez);
}

int best_path(int N, int K, int H[][2], int W[]) {
    for(int i = 0; i < N - 1; ++i) {
        L[H[i][0] + 1].push_back({H[i][1] + 1, W[i]});
        L[H[i][1] + 1].push_back({H[i][0] + 1, W[i]});
    }
    int rez = numeric_limits<int>::max() / 4;
    desc(1, 0, K, rez);
    if(rez == numeric_limits<int>::max() / 4) rez = -1;
    return rez;
}

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