제출 #422403

#제출 시각아이디문제언어결과실행 시간메모리
422403milleniumEeee공장들 (JOI14_factories)C++11
15 / 100
8071 ms116572 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 dist[3][MAXN]; void dijkstra(vector <int> start, ll *min_dist) { fill(min_dist, min_dist + n + 123, -1); priority_queue <pair<ll, int>> pq; for (int el : start) { min_dist[el] = 0; pq.push({0, el}); } while (!pq.empty()) { ll cost = -pq.top().fr; int v = pq.top().sc; pq.pop(); if (cost > min_dist[v]) { continue; } for (auto [to, dist] : g[v]) { if (min_dist[to] == -1 || min_dist[to] > cost + dist) { min_dist[to] = cost + dist; pq.push({-min_dist[to], to}); } } } } bool ok = 1; ll Query(int S, int X[], int T, int Y[]) { if (!ok) { vector <int> start_s, start_t; for (int i = 0; i < S; i++) { start_s.pb(X[i]); } for (int i = 0; i < T; i++) { start_t.pb(Y[i]); } dijkstra(start_s, dist[1]); dijkstra(start_t, dist[2]); ll ans = INF; for (int i = 0; i < n; i++) { ans = min(ans, dist[1][i] + dist[2][i]); } return ans; } ok &= (S <= 10 && T <= 10); if (ok) { 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; } else { vector <int> start_s, start_t; for (int i = 0; i < S; i++) { start_s.pb(X[i]); } for (int i = 0; i < T; i++) { start_t.pb(Y[i]); } dijkstra(start_s, dist[1]); dijkstra(start_t, dist[2]); ll ans = INF; for (int i = 0; i < n; i++) { ans = min(ans, dist[1][i] + dist[2][i]); } return ans; } }

컴파일 시 표준 에러 (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]) {
      |            ^
factories.cpp: In function 'void dijkstra(std::vector<int>, long long int*)':
factories.cpp:96:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for (auto [to, dist] : g[v]) {
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...