#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include "race.h" #include <algorithm> #include <cassert> #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 constexpr int up = 1e6 + 1; int mp[up], last[up]; struct CentroiddeComposition { int _n_, _k_, _ans_, _cur_; vector<vector<pair<int, int>>> g; vector<bool> removed; vector<int> subSize, distFromCentroid, nodeFromCentroid; CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(1) { removed.assign(_n + 1, false); distFromCentroid.assign(_n + 1, INFi); nodeFromCentroid.assign(_n + 1, INFi); subSize.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??? int target = _k_ - distFromCentroid[v]; if (last[target] != _cur_) { mp[target] = INFi; last[target] = _cur_; } _ans_ = min(_ans_, mp[target] + 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); } } void addDistFromCentoid(int v, int pa) { if (distFromCentroid[v] > _k_) { return; } if (last[distFromCentroid[v]] != _cur_) { mp[distFromCentroid[v]] = INFi; last[distFromCentroid[v]] = _cur_; } mp[distFromCentroid[v]] = min(mp[distFromCentroid[v]], nodeFromCentroid[v]); for (const auto &[u, w] : g[v]) { if (pa == u || removed[u]) continue; addDistFromCentoid(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; } void solve(int centroid) { // 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); // mp.assign(_k_ + 1, INFi);// XXX: Can't assign _cur_++; if (_ans_ == 1) return; last[0] = _cur_; mp[0] = 0; for (const auto &[u, w] : g[centroid]) { if (removed[u]) continue; nodeFromCentroid[u] = 1; distFromCentroid[u] = w; getDistFromCentroid(u, centroid); addDistFromCentoid(u, centroid); } } void build(int v = 0) { // TODO: Inside int centroid = findCentroid(v, getSubSize(v) >> 1); removed[centroid] = true; solve(centroid); for (const auto &[u, w] : g[centroid]) { if (removed[u]) continue; build(u); // WARNING: should it be id + 1 or id ??? } } }; int best_path(int N, int K, int H[][2], int L[]) { dbg(N); // 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.build(0); if (t._ans_ == INFi) t._ans_ = -1; return t._ans_; } // Attack on titan<3 // Just Imaginary /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */

race.cpp:21:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   21 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
race.cpp:28:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   28 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
race.cpp:30:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   30 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
race.cpp:44:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   44 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
In file included from race.cpp:47:
race.h:1:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |                                                ^
race.h:1:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.h:1:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:82:84: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   82 |     CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(1) {
      |                                                                                    ^
race.cpp:82:84: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:82:84: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:82:84: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:88:38: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   88 |     int getSubSize(int v, int pa = -1) {
      |                                      ^
race.cpp:88:38: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:88:38: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:88:38: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:99:43: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   99 |     void getDistFromCentroid(int v, int pa) {
      |                                           ^
race.cpp:99:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:99:43: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:99:43: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:117:42: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  117 |     void addDistFromCentoid(int v, int pa) {
      |                                          ^
race.cpp:117:42: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:117:42: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:117:42: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:133:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  133 |     int findCentroid(int v, int half, int pa = -1) {
      |                                                  ^
race.cpp:133:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:133:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:133:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:143:28: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  143 |     void solve(int centroid) { // INFO: Centroid ucun cavab
      |                            ^
race.cpp:143:28: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:143:28: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:143:28: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:166:25: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  166 |     void build(int v = 0) { // TODO: Inside
      |                         ^
race.cpp:166:25: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:166:25: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:166:25: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:178:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  178 | int best_path(int N, int K, int H[][2], int L[]) {
      |                                                ^
race.cpp:178:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:178:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:178:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]