Submission #1317329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317329		AzeTurk810	Race (IOI11_race)	C++20	0 / 100	0 ms	332 KiB

race

#include "race.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <map>
#include <utility>
#include <vector>
// #include <algo.hpp>
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

struct CentroiddeComposition {
    int _n_, _k_, _ans_;
    vector<vector<pair<int, int>>> g;
    vector<bool> removed;
    vector<int> subSize, distFromCentroid, nodeFromCentroid;
    vector<vector<int>> level;
    map<int, int> mp;
    CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi) {
        removed.assign(_n + 1, false);
        distFromCentroid.assign(_n + 1, INFi);
        nodeFromCentroid.assign(_n + 1, INFi);
        subSize.resize(_n + 1);
        level.resize(_n + 1);
    }
    int getSubSize(int v, int pa = -1) {
        subSize[v] = 1;
        for (const auto &[u, w] : g[v]) {
            if (u == pa || removed[u])
                continue;
            getSubSize(u, v);
            subSize[v] += subSize[u];
        }
        return subSize[v];
    }

    void getDistFromCentroid(int v, int pa) {
        if (distFromCentroid[v] > _k_)      // XXX: it can be in the same subtree
            return;
        // INFO: is it in other side of centroid???
        if (distFromCentroid[v] <= _k_) {
            int target = _k_ - distFromCentroid[v];
            if (mp.find(target) != mp.end()) {
                _ans_ = min(_ans_, mp[target] + nodeFromCentroid[v]);
            }
            if (mp.find(distFromCentroid[v]) == mp.end())
                mp[distFromCentroid[v]] = nodeFromCentroid[v];
            mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]);
        }
        for (const auto &[u, w] : g[v]) {
            if (pa == u || removed[u])
                continue;
            distFromCentroid[u] = distFromCentroid[v] + w;
            nodeFromCentroid[u] = nodeFromCentroid[v] + 1;
            getDistFromCentroid(u, v);
        }
    }

    int findCentroid(int v, int half, int pa = -1) {
        for (const auto &[u, w] : g[v]) {
            if (u == pa || removed[u] || subSize[u] <= half) {
                continue;
            }
            return findCentroid(u, half, v);
        }
        return v;
    }

    int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
        // WARNING: You must initilaze before getDistFromCentroid Manualy
        // nodeFromCentroid[v] = 0;
        // distFromCentroid[v] = 0;
        // mp.clear();
        // mp_same.clear();
        // getDistFromCentroid(v, -1);
        nodeFromCentroid[centroid] = 0;
        distFromCentroid[centroid] = 0;
        mp.clear();
        mp[0] = 0;
        getDistFromCentroid(centroid, -1);
        return _ans_;
    }

    int build(int v = 0, int id = 0) { // TODO: Inside
        int centroid = findCentroid(v, getSubSize(v) >> 1);
        removed[centroid] = true;
        solve(centroid, subSize[v]);
        for (const auto &[u, w] : g[centroid]) {
            if (removed[u])
                continue;
            level[id + 1].push_back(build(u, id + 1)); // WARNING: should it be id + 1 or id  ???
        }
        return centroid;
    }
};

int best_path(int N, int K, int H[][2], int L[]) {
    // return 0;
    vector<vector<pair<int, int>>> g(N);
    for (int i = 0; i < N - 1; i++) {
        const int &u = H[i][0], &v = H[i][1], &w = L[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    CentroiddeComposition t(N, g, K);
    t.level[0].push_back(t.build(0));
    if (t._ans_ == INFi)
        t._ans_ = -1;
    return t._ans_;
}

// Attack on titan<3
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/

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