Submission #1213429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213429		musanna47	Race (IOI11_race)	C++20	100 / 100	340 ms	30916 KiB

race

// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)

#include "bits/stdc++.h"

using namespace std;


#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)


template<typename T1, typename T2>
using P = pair<T1, T2>;
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using VVV = V<V<V<T>>>;
template<typename T>
using VVVV = V<V<V<V<T>>>>;


using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;


template<typename T>
void pout(T &a, string sep = " ", string fin = "\n") {
    cout << a.first << sep << a.second << fin;
}

template<typename T>
void print(T &a, ll l, ll r, string sep = " ", string fin = "\n") {
    for (ll i = l; i <= r; i++)
        cout << a[i] << sep;
    cout << fin;
}

template<typename T>
void printPairs(T &a, ll l, ll r, string fin = "\n") {
    for (ll i = l; i <= r; i++)
        pout(a[i]);
    cout << fin;
}

template<typename T>
void printAll(T &a, string sep = " ", string fin = "\n") {
    for (auto &ele: a)
        cout << ele << sep;
    cout << fin;
}

template<typename T>
void printPairsAll(T &a, string fin = "\n") {
    for (auto &ele: a)
        pout(ele);
    cout << fin;
}

template<typename... Args>
void read(Args &... args) {
    ((cin >> args), ...);
}

template<typename... Args>
void out(Args... args) {
    ((cout << args << " "), ...);
}

template<typename... Args>
void outln(Args... args) {
    ((cout << args << " "), ...);
    cout << nl;
}

template<typename T>
void vin(T &a, ll l, ll r) {
    for (ll i = l; i <= r; i++)
        cin >> a[i];
}


const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LL_INF = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-12;


const int MAXN = 2e5;
const int MAXK = 1e6;
V<pii> adj[MAXN + 1];
int subsize[MAXN + 1];
bitset<MAXN + 1> done;
int cnt[MAXK + 1];


int ans = INF;
int n = 0, k = 0;


void getSubSize(int i, int par) {
    subsize[i] = 1;
    for (auto &[child, w]: adj[i]) {
        if (child != par && !done[child]) {
            getSubSize(child, i);
            subsize[i] += subsize[child];
        }
    }
}

void fillCnt(int node, int par, int depth, int dist) {
    if (dist > k) return;
    cnt[dist] = min(cnt[dist], depth);
    for (auto &[child, w]: adj[node]) {
        if (child != par && !done[child]) {
            fillCnt(child, node, depth + 1, dist + w);
        }
    }
}

void getCnt(int node, int par, int depth, int dist) {
    if (dist > k) return;
    ans = min(ans, depth + cnt[k - dist]);
    for (auto &[child, w]: adj[node]) {
        if (child != par && !done[child]) {
            getCnt(child, node, depth + 1, dist + w);
        }
    }
}

void resetCnt(int node, int par, int depth, int dist) {
    if (dist > k) return;
    cnt[dist] = INF;
    for (auto &[child, w]: adj[node]) {
        if (child != par && !done[child]) {
            resetCnt(child, node, depth + 1, dist + w);
        }
    }
}

void centroidDecomp(int node) {
    // Get subtree sizes
    getSubSize(node, -1);

    // Get Centroid
    int centroid = node, par = -1;
    while (true) {
        bool stop = true;
        for (auto &[child, w]: adj[centroid]) {
            if (child != par && !done[child]) {
                if (subsize[child] > subsize[node] / 2) {
                    stop = false;
                    par = centroid, centroid = child;
                    break;
                }
            }
        }
        if (stop)
            break;
    }

    // Mark centroid as done
    done[centroid] = true;
    cnt[0] = 0;

    // Perform task / query
    for (auto &[child, w]: adj[centroid]) {
        if (!done[child]) {
            getCnt(child, centroid, 1, w);
            fillCnt(child, centroid, 1, w);
        }
    }

    // Reset Cnt
    for (auto &[child, w]: adj[centroid]) {
        if (!done[child]) {
            resetCnt(child, centroid, 1, w);
        }
    }

    // Check next subtree
    for (auto &[child, w]: adj[centroid]) {
        if (!done[child])
            centroidDecomp(child);
    }

}


int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    REPF(i, 0, n - 2) {
        auto [u, v] = H[i];
        auto w = L[i];
        adj[u + 1].emplace_back(v + 1, w);
        adj[v + 1].emplace_back(u + 1, w);
    }

    fill(cnt + 1, cnt + MAXK + 1, INF);

    centroidDecomp(1);

    return (ans == INF ? -1 : ans);
}

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