Submission #922258

#TimeUsernameProblemLanguageResultExecution timeMemory
922258Beerus13Factories (JOI14_factories)C++14
100 / 100
4462 ms372804 KiB
#include <bits/stdc++.h> // #include "factories.h" using namespace std; #define ll long long #define pii pair<int, ll> const int N = 5e5 + 5; const ll inf = 1e15; int n, q, S, T, centroid; int sz[N], vt[N]; vector<pii> g[N], ancestors[N]; bool del[N]; ll dp[N]; int dfs_size(int u, int p = 0) { sz[u] = 1; for(auto [v, w] : g[u]) if(v != p && !del[v]) { sz[u] += dfs_size(v, u); } return sz[u]; } int find_centroid(int u, int p, int num) { for(auto [v, w] : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num); return u; } void dfs_centroid(int u, int par, ll dis) { for(auto [v, w] : g[u]) if(v != par && !del[v]) dfs_centroid(v, u, dis + w); ancestors[u].emplace_back(centroid, dis); } void decomposition(int u) { centroid = find_centroid(u, 0, dfs_size(u)); del[centroid] = 1; dfs_centroid(centroid, centroid, 0); for(auto [v, w] : g[centroid]) { if(!del[v]) decomposition(v); } } void add(int u) { for(auto [v, w] : ancestors[u]) dp[v] = min(dp[v], w); } void remove(int u) { for(auto [v, w] : ancestors[u]) dp[v] = inf; } ll get(int u) { ll ans = inf; for(auto [v, w] : ancestors[u]) ans = min(ans, w + dp[v]); return ans; } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N - 1; ++i) { A[i]++; B[i]++; g[A[i]].emplace_back(B[i], D[i]); g[B[i]].emplace_back(A[i], D[i]); } for(int i = 1; i <= N; ++i) dp[i] = inf; decomposition(1); } ll Query(int S, int X[], int T, int Y[]) { for (int i = 0; i < S; i++) add(X[i] + 1); ll ans = 1e15; for (int i = 0; i < T; i++) ans = min(ans, get(Y[i] + 1)); for (int i = 0; i < S; i++) remove(X[i] + 1); return ans; } // https://oj.uz/problem/view/JOI14_factories

Compilation message (stderr)

factories.cpp: In function 'int dfs_size(int, int)':
factories.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [v, w] : g[u]) if(v != p && !del[v]) {
      |              ^
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for(auto [v, w] : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
      |              ^
factories.cpp: In function 'void dfs_centroid(int, int, long long int)':
factories.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [v, w] : g[u]) if(v != par && !del[v]) dfs_centroid(v, u, dis + w);
      |              ^
factories.cpp: In function 'void decomposition(int)':
factories.cpp:37:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for(auto [v, w] : g[centroid]) {
      |              ^
factories.cpp: In function 'void add(int)':
factories.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [v, w] : ancestors[u]) dp[v] = min(dp[v], w);
      |              ^
factories.cpp: In function 'void remove(int)':
factories.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [v, w] : ancestors[u]) dp[v] = inf;
      |              ^
factories.cpp: In function 'long long int get(int)':
factories.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto [v, w] : ancestors[u]) ans = min(ans, w + dp[v]);
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...