Submission #821814

#TimeUsernameProblemLanguageResultExecution timeMemory
821814PanosPaskFactories (JOI14_factories)C++14
100 / 100
3636 ms352172 KiB
#include "factories.h" #include "vector" #include "math.h" #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const ll INF = 1e18; typedef pair<int, ll> pi; int N; vector<int> subtree_size; vector<vector<pi>> adj_list; vector<bool> removed; // Ancestors in centroid tree(at most logN) vector<vector<pi>> ancestors; vector<ll> min_source_dist; int calc_sb_size(int node, int par, ll d, int anc) { subtree_size[node] = 1; for (auto [neigh, w] : adj_list[node]) { if (neigh != par && !removed[neigh]) { subtree_size[node] += calc_sb_size(neigh, node, d + w, anc); } } if (anc != -1) ancestors[node].pb(mp(anc, d)); return subtree_size[node]; } int find_centroid(int node, int par, int sz) { for (auto [neigh, w] : adj_list[node]) { if (!removed[neigh] && neigh != par && subtree_size[neigh] > sz / 2) return find_centroid(neigh, node, sz); } return node; } void centroid_decompose(int node) { int c = find_centroid(node, -1, subtree_size[node]); removed[c] = true; for (auto [neigh, w] : adj_list[c]) { if (removed[neigh]) continue; calc_sb_size(neigh, -1, w, c); } for (auto [neigh, w] : adj_list[c]) { if (removed[neigh]) continue; centroid_decompose(neigh); } return; } void Init(int n, int A[], int B[], int D[]) { N = n; adj_list.resize(N); subtree_size.resize(N); min_source_dist.assign(N, INF); removed.resize(N); ancestors.resize(N); for (int i = 0; i < N - 1; i++) { adj_list[A[i]].pb(mp(B[i], D[i])); adj_list[B[i]].pb(mp(A[i], D[i])); } calc_sb_size(0, -1, 0, -1); centroid_decompose(0); } long long Query(int S, int X[], int T, int Y[]) { removed.assign(N, false); ll res = INF; for (int i = 0; i < S; i++) { int v = X[i]; // Iterate over all ancestors of v min_source_dist[v] = 0; for (auto [u, d] : ancestors[v]) { min_source_dist[u] = min(min_source_dist[u], d); } } for (int i = 0; i < T; i++) { int v = Y[i]; res = min(res, min_source_dist[v]); for (auto [u, d] : ancestors[v]) { res = min(res, d + min_source_dist[u]); } } for (int i = 0; i < S; i++) { int v = X[i]; min_source_dist[v] = INF; for (auto [u, d] : ancestors[v]) min_source_dist[u] = INF; } return res; }

Compilation message (stderr)

factories.cpp: In function 'int calc_sb_size(int, int, ll, int)':
factories.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for (auto [neigh, w] : adj_list[node]) {
      |               ^
factories.cpp: In function 'void centroid_decompose(int)':
factories.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp:63:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for (auto [neigh, w] : adj_list[c]) {
      |               ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:103:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         for (auto [u, d] : ancestors[v]) {
      |                   ^
factories.cpp:112:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |         for (auto [u, d] : ancestors[v]) {
      |                   ^
factories.cpp:121:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |         for (auto [u, d] : ancestors[v])
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...