Submission #1140823

#TimeUsernameProblemLanguageResultExecution timeMemory
1140823DaciejMaciejRace (IOI11_race)C++20
0 / 100
7 ms14400 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld; template <class T> using VV = vector<vector<T>>; using VI = vector<int>; using VVI = vector<vector<int>>; using VL = vector<long long>; using VVL = vector<vector<long long>>; using VC = vector<char>; using VVC = vector<vector<char>>; using VB = vector<bool>; using VVB = vector<vector<bool>>; using VD = vector<double>; using VVD = vector<vector<double>>; using PII = pair<int, int>; using PLL = pair<long long, long long>; using PIL = pair<int, long long>; using PLI = pair<long long, int>; using VPII = vector<pair<int, int>>; using VPLL = vector<pair<long long, long long>>; #define LINE '\n' #define SPACE ' ' #define PB push_back #define FOR(i, a, b) for (int i = (a); i < (int(b)); i++) #define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++) #define ALL(x) x.begin(), x.end() #define RALL(x) x.rbegin(), x.rend() #define sq(a) ((a) * (a)) #define sz(x) ((int)x.size()) #define fastio() \ ios_base::sync_with_stdio(false); \ cin.tie(nullptr); \ cout.tie(nullptr) #define debug(x) cerr << #x << " = " << x << endl; const ll MOD = 1e9 + 7; template <class T> inline void maxi(T &a, T b) { a = max(a, b); } template <class T> inline void mini(T &a, T b) { a = min(a, b); } template <class T> inline void addi(T &a, T b) { a = (a + b) % MOD; } template <class T> inline void subi(T &a, T b) { a = (a - b + MOD) % MOD; } template <class T> inline T add(T a, T b) { return (a + b) % MOD; } template <class T> inline T sub(T a, T b) { return (a - b + MOD) % MOD; } template <class T> inline T mul(T a, T b) { return ((a % MOD) * (b % MOD)) % MOD; } constexpr ll binpow(ll a, ll b, ll mod) { ll res = 1; while (b > 0) { if (b & 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } const int INF = 1e9; const int MAX_N = 2e5 + 3; VPII g[MAX_N]; int n, k; ll sum[MAX_N], depth[MAX_N], sz[MAX_N]; map<ll, ll> mp[MAX_N]; ll ans = 1e9; void dfs(int c, int p) { depth[c] = depth[p] + 1; mp[c][sum[c]] = depth[c]; // need it later in dfs2 sz[c] = 1; for(auto [it, edge] : g[c]) { if(it == p) continue; sum[it] = sum[c] + ll(edge); dfs(it, c); sz[c] += sz[it]; } } void dfs2(int c, int p) { ll target = k + 2 * sum[c]; for(auto [it, edge] : g[c]) { if(it == p) continue; dfs2(it, c); if(sz(mp[it]) > sz(mp[c])) swap(mp[c], mp[it]); for(auto [sm, edges] : mp[it]) { if(mp[c].find(target-sm) != mp[c].end()) { mini(ans, mp[c][target-sm] + edges); } } for(auto [sm, edges] : mp[it]) { if(mp[c].find(sm) != mp[c].end()) { mini(mp[c][sm], edges); } else { mp[c][sm] = edges; } } } } int best_path(int N, int K, int H[][2], int L[]) { if(k == 1) return 0; n = N; k = K; FOR(i, 0, n) { int u = H[i][0], v = H[i][1]; g[u].PB({v, L[i]}); g[v].PB({u, L[i]}); } depth[0] = -1; dfs(0, 0); dfs2(0, 0); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...