제출 #422537

#제출 시각아이디문제언어결과실행 시간메모리
422537milleniumEeee공장들 (JOI14_factories)C++14
33 / 100
8096 ms160488 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; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int get_rand() { ll x = rnd(); x %= (ll)1e9; if (x < 0) { x = -x; } return x; } int gen(int l, int r) { return l + (get_rand() % (r - l + 1)); } vector <pii> g[MAXN]; int n; int pr[MAXN][L + 1]; ll d[MAXN]; int tin[MAXN], tout[MAXN], tiktak; bool used[MAXN]; int sub[MAXN]; vector <int> G[MAXN]; int Gpar[MAXN]; ll opt[MAXN]; 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 calc(int v, int par) { sub[v] = 1; for (auto [to, dist] : g[v]) { if (to != par && !used[to]) { calc(to, v); sub[v] += sub[to]; } } } int find_centroid(int v, int par, int sz) { for (auto [to, dist] : g[v]) { if (to != par && sub[to] > sz / 2 && !used[to]) { return find_centroid(to, v, sz); } } return v; } void build(int v, int par) { calc(v, -1); int center = find_centroid(v, -1, sub[v]); used[center] = 1; if (par != -1) { G[center].pb(par); G[par].pb(center); Gpar[center] = par; } for (auto [to, dist] : g[center]) { if (!used[to]) { build(to, center); } } } void Init(int N, int A[], int B[], int D[]) { memset(Gpar, -1, sizeof(Gpar)); fill(opt, opt + MAXN, INF); n = N; for (int i = 0; i < n - 1; 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); build(0, -1); } void upd(int v, int type) { if (type == 1) { int cur = v; while (1) { if (cur == -1) { break; } opt[cur] = min(opt[cur], get_dist(cur, v)); cur = Gpar[cur]; } } else { int cur = v; while (1) { if (cur == -1) { break; } opt[cur] = INF; cur = Gpar[cur]; } } } ll get(int v) { ll ret = INF; int cur = v; while (1) { if (cur == -1) { break; } ret = min(ret, get_dist(v, cur) + opt[cur]); cur = Gpar[cur]; } return ret; } ll Query(int S, int X[], int T, int Y[]) { ll ans = INF; for (int i = 0; i < S; i++) { upd(X[i], 1); } for (int i = 0; i < T; i++) { ans = min(ans, get(Y[i])); } for (int i = 0; i < S; i++) { upd(X[i], -1); } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

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