Submission #422382

#TimeUsernameProblemLanguageResultExecution timeMemory
422382milleniumEeeeFactories (JOI14_factories)C++11
18 / 100
8032 ms116548 KiB
#include "factories.h" #ifndef EVAL #include "grader.cpp" #endif #include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define ll long long using namespace std; const ll INF = 1e18; const int MAXN = (int)5e5 + 5; const int MAXQ = (int)1e5 + 5; const int L = 20; vector <pii> g[MAXN]; int n; int pr[MAXN][L + 1]; ll d[MAXN]; int tin[MAXN], tout[MAXN], tiktak; void precalc(int v, int par, ll len) { tin[v] = ++tiktak; pr[v][0] = par; d[v] = len; for (int lv = 1; lv <= L; lv++) { pr[v][lv] = pr[pr[v][lv - 1]][lv - 1]; } for (auto [to, dist] : g[v]) { if (to == par) { continue; } precalc(to, v, len + dist); } tout[v] = tiktak; } bool father(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a]; } int get_lca(int a, int b) { if (father(a, b)) { return a; } if (father(b, a)) { return b; } for (int lv = L; lv >= 0; lv--) { if (!father(pr[a][lv], b)) { a = pr[a][lv]; } } return pr[a][0]; } ll get_dist(int a, int b) { return d[a] + d[b] - (2ll * d[get_lca(a, b)]); } void Init(int N, int A[], int B[], int D[]) { n = N; for (int i = 0; i < n; i++) { int u = A[i]; int v = B[i]; int dist = D[i]; g[u].pb({v, dist}); g[v].pb({u, dist}); } precalc(0, 0, 0); } ll Query(int S, int X[], int T, int Y[]) { ll ans = INF; for (int i = 0; i < S; i++) { for (int j = 0; j < T; j++) { ans = min(ans, get_dist(X[i], Y[j])); } } return ans; }

Compilation message (stderr)

factories.cpp: In function 'void precalc(int, int, long long int)':
factories.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for (auto [to, dist] : g[v]) {
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...