Submission #383960

#TimeUsernameProblemLanguageResultExecution timeMemory
383960wind_reaperFactories (JOI14_factories)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; const int MXN = 500000; const int LOG = 20; const int64_t INF = 1e18; vector<array<int, 2>> g[MXN]; int sz[MXN], centroid[MXN], up[LOG][MXN], tin[MXN], tout[MXN]; int64_t depth[MXN], best[MXN]; vector<bool> vis(MXN, 0); int timer = 0; void dfs(int node, int par, int dist){ tin[node] = timer++; depth[node] = depth[par] + int64_t(dist); up[0][node] = par; for(int i = 1; i < LOG; i++) up[i][node] = up[i-1][up[i-1][node]]; for(auto& [v, d] : g[node]){ if(v == par) continue; dfs(v, node, d); sz[node] += sz[v]; } tout[node] = timer; } inline bool isAncestor(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; } int lca(int u, int v){ if(isAncestor(u, v)) return u; if(isAncestor(v, u)) return v; for(int i = LOG-1; i >= 0; --i){ if(!isAncestor(up[i][u], v)) u = up[i][u]; } return up[0][u]; } inline int64_t dist(int u, int v){ return depth[u] + depth[v] - 2*depth[lca(u, v)]; } void decompose(int node, int c){ int inv = -1, szl = (sz[node] >> 1); for(auto& [v, d] : g[node]){ if(!vis[v] && sz[v] > szl){ inv = v; break; } } if(inv != -1){ sz[node] -= sz[inv]; sz[inv] += sz[node]; return decompose(inv, c); } vis[p] = 1; centroid[p] = c; for(auto& [v, d] : g[node]){ if(!vis[v]){ centroid[v] = p; decompose(v, p); } } } vector<int> hit; void update(int node){ int v = node; while(v != -1){ best[v] = min(best[v], dist(node, v)); hit.push_back(v); v = centroid[v]; } } int64_t query(int node){ int64_t ans = INF; int v = node; while(v != -1){ ans = min(ans, best[v] + dist(v, node)); } return ans; } void Init(int n, int A[], int B[], int D[]){ for(int i = 0; i < n; i++) best[i] = INF; for(int i = 0; i < n - 1; i++){ g[A[i]].push_back({B[i], D[i]}); g[B[i]].push_back({A[i], D[i]}); } dfs(0, 0, 0); decompose(0, -1); } long long Query(int S, int X[], int T, int Y[]){ for(int i = 0; i < S; i++) update(X[i]); int64_t ans = INF; for(int i = 0; i < T; i++) ans = min(ans, query(Y[i])); for(int i : hit) best[i] = INF; hit.clear(); return ans; }

Compilation message (stderr)

factories.cpp: In function 'void decompose(int, int)':
factories.cpp:72:6: error: 'p' was not declared in this scope
   72 |  vis[p] = 1;
      |      ^