Submission #38080

#TimeUsernameProblemLanguageResultExecution timeMemory
38080MatheusLealVFactories (JOI14_factories)C++14
15 / 100
5883 ms268940 KiB
#include <bits/stdc++.h> #include "factories.h" #define Ni 500050 #define logn 20 #define inf 200000000000000000 #define f first #define s second using namespace std; typedef long long ll; typedef pair<int, int> pii; int n, q, nivel[Ni], block[Ni], sz[Ni], tot, pai[Ni], root, tmp = 1, ini[Ni], deep[2*Ni]; ll dist[Ni], ans[Ni]; vector<pii> grafo[Ni]; vector<int> tree[Ni], euler; pii best, dp[2*Ni][logn]; int last_upd[Ni], cnt_upd = 1; inline void build() { for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]); for(int j = 1; j < logn; j++) { for(int i = 0; i < euler.size(); i++) { if(i + (1<<(j - 1) < 2*Ni)) dp[i][j] = min(dp[i][j - 1], dp[ i + (1<<(j - 1)) ][j - 1]); else dp[i][j] = dp[i][j - 1]; } } } inline int query(int l, int r) { if(l == r) return euler[l]; int e = 31-__builtin_clz(r-l); return min(dp[l][e], dp[r - (1<<e) + 1][e]).s; } inline void dfs(int x, int p) { if(ini[x] == 0) ini[x] = tmp; euler.push_back(x); tmp ++; for(int i = 0; i < grafo[x].size(); i++) { int v = grafo[x][i].f; ll peso = (ll)grafo[x][i].s; if(v == p) continue; nivel[v] = nivel[x] + 1; dist[v] = dist[x] + peso; dfs(v, x); euler.push_back(x); tmp ++; } } inline void init() { dfs(1, 1); for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]]; build(); } inline int lca(int a, int b) { return query(min(ini[a] - 1, ini[b] - 1), max(ini[a] - 1, ini[b] - 1)); } inline int tam(int x, int p) { sz[x] = 1; for(int i = 0; i < grafo[x].size(); i++) { int v = grafo[x][i].f; if(v == p || block[v]) continue; sz[x] += tam(v, x); } return sz[x]; } inline void split(int x, int p) { int maior = tot - sz[x]; for(int i = 0; i < grafo[x].size(); i++) { int v = grafo[x][i].f; if(v == p || block[v]) continue; split(v, x); maior = max(maior, sz[v]); } if(maior < best.f) best = pii(maior, x); } inline int find_centroid(int x) { tot = tam(x, x); best = pii(2*Ni, 0); split(x, x); return best.s; } inline int decomp(int x) { x = find_centroid(x); block[x] = 1; for(auto v: grafo[x]) { if(block[v.f]) continue; v.f = decomp(v.f); tree[x].push_back(v.f); tree[v.f].push_back(x); } return x; } inline void dfs2(int x, int p) { pai[x] = p; for(auto v: tree[x]) { if(v == p) continue; pai[v] = x; dfs2(v, x); } } inline ll distancia(int a, int b) { return dist[a] + dist[b] - 2*dist[lca(a, b)]; } inline void paint(int x) { ans[x] = 0; last_upd[x] = cnt_upd; int u = x; while(1) { if(last_upd[pai[x]] != cnt_upd) ans[pai[x]] = distancia(u, pai[x]); else ans[pai[x]] = min(ans[pai[x]], distancia(u, pai[x])); last_upd[pai[x]] = cnt_upd; if(x == pai[x]) return; x = pai[x]; } } inline void clear(int x) { ans[x] = inf; int u = x; while(1) { ans[pai[x]] = inf; if(x == pai[x]) return; x = pai[x]; } } ll query(int x) { int u = x; ll resp = inf; if(last_upd[x] == cnt_upd) resp = min(resp, ans[x]); while(1) { if(last_upd[x] == cnt_upd) resp = min(resp, distancia(x, u) + ans[x]); if(x == pai[x]) return resp; x = pai[x]; } } void Init(int N_, int A[], int B[], int D[]) { n = N_; for(int i = 0; i < Ni; i++) ans[i] = inf; for(int i = 0; i < n - 1; i++) { int a = A[i], b = B[i], c = D[i]; a++, b++; grafo[a].push_back(pii(b, c)); grafo[b].push_back(pii(a, c)); } init(); root = decomp(1); dfs2(root, root); } ll Query(int S, int X[], int T, int Y[]) { ll ans = inf; ++cnt_upd; for(int i = 0; i < S ; i++) paint(X[i] + 1); for(int i = 0; i < T; i++) ans = min(ans, query(Y[i] + 1)); //for(int i = 0; i < S; i++) clear(X[i] + 1); return ans; }

Compilation message (stderr)

factories.cpp: In function 'void build()':
factories.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]);
                    ^
factories.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < euler.size(); i++)
                        ^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++)
                   ^
factories.cpp: In function 'void init()':
factories.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]];
                   ^
factories.cpp: In function 'int tam(int, int)':
factories.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < grafo[x].size(); i++)
                      ^
factories.cpp: In function 'void split(int, int)':
factories.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < grafo[x].size(); i++)
                      ^
factories.cpp: In function 'void clear(int)':
factories.cpp:200:6: warning: unused variable 'u' [-Wunused-variable]
  int u = x;
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...