#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; vector<vector<int>> level; 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); 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 (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; } 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); // mp.assign(_k_ + 1, INFi);// XXX: Can't assign _cur_++; last[0] = _cur_; mp[0] = 0; for (const auto &[u, w] : g[centroid]) { nodeFromCentroid[u] = 1; distFromCentroid[u] = w; getDistFromCentroid(u, centroid); addDistFromCentoid(u, centroid); } 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 /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */

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:83:84: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   83 |     CentroiddeComposition(int _n, vector<vector<pair<int, int>>> &_g, const int &_k) : g(_g), _n_(_n), _k_(_k), _ans_(INFi), _cur_(1) {
      |                                                                                    ^
race.cpp:83:84: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:83:84: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:83:84: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   90 |     int getSubSize(int v, int pa = -1) {
      |                                      ^
race.cpp:90:38: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:90:38: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  101 |     void getDistFromCentroid(int v, int pa) {
      |                                           ^
race.cpp:101:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:101:43: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  121 |     void addDistFromCentoid(int v, int pa) {
      |                                          ^
race.cpp:121:42: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:121:42: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  137 |     int findCentroid(int v, int half, int pa = -1) {
      |                                                  ^
race.cpp:137:50: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:137:50: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  147 |     int solve(int centroid, int sizeoftree) { // INFO: Centroid ucun cavab
      |                                           ^
race.cpp:147:43: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:147:43: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  167 |     int build(int v = 0, int id = 0) { // TODO: Inside
      |                                    ^
race.cpp:167:36: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:167:36: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  180 | int best_path(int N, int K, int H[][2], int L[]) {
      |                                                ^
race.cpp:180:48: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
race.cpp:180:48: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]