#include "race.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define ff(i,a,b) for(int i=a;i<=b;i++) #define fb(i,b,a) for(int i=b;i>=a;i--) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,int> pii; const int maxn = 2000005; const int inf = 1e9 + 5; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // os.order_of_key(k) the number of elements in the os less than k // *os.find_by_order(k) print the k-th smallest number in os(0-based) int n, k; vector<pii> g[maxn]; int rez = inf; map<int,int> dfs(int v, int p, int duz, int pw){ map<int,int> dt; dt[pw] = duz; // cout << "v: " << v << endl; // cout << "duz: " << duz << endl; // cout << "pw: " << pw << endl; // cout << endl; for(auto c : g[v]){ int u = c.fi; int w = c.se; if(u != p){ auto pomdt = dfs(u, v, duz + 1, pw + w); int x = v, y = u; if(sz(dt) < sz(pomdt))swap(dt, pomdt); for(auto c : pomdt){ if(dt.count(k - c.fi + 2 * pw))rez = min(rez, dt[k - c.fi + 2 * pw] + c.se - 2 * duz); if(!dt.count(c.fi))dt[c.fi] = c.se; else dt[c.fi] = min(dt[c.fi], c.se); } } } // cout << "v: " << v << endl; // for(auto c : dt[v])cout << c.fi << " " << c.se << endl; // cout << "-----------------------------" << endl; return dt; } int best_path(int N, int K, int H[][2], int L[]){ n = N; k = K; ff(i,0,n - 2){ int u = H[i][0] + 1; int v = H[i][1] + 1; int w = L[i]; g[u].pb({v, w}); g[v].pb({u, w}); } rez = inf; dfs(1, -1, 1, 0); if(rez == inf)return -1; else return rez; } //int main() //{ // ios::sync_with_stdio(false); // cout.tie(nullptr); // cin.tie(nullptr); // cin >> n >> k; // ff(i,1,n - 1){ // int u, v, w; // cin >> u >> v >> w; // g[u].pb({v, w}); // g[v].pb({u, w}); // } // dfs(1, -1, 1, 0); // cout << rez << endl; // return 0; //} /** 11 12 1 2 3 1 3 4 3 4 5 4 5 4 5 6 6 1 7 3 7 8 2 7 9 5 9 10 6 9 11 7 // probati bojenje sahovski ili slicno **/

race.cpp: In function 'std::map<int, int> dfs(int, int, int, int)':
race.cpp:46:17: warning: unused variable 'x' [-Wunused-variable]
   46 |             int x = v, y = u;
      |                 ^
race.cpp:46:24: warning: unused variable 'y' [-Wunused-variable]
   46 |             int x = v, y = u;
      |                        ^