Submission #56996

#TimeUsernameProblemLanguageResultExecution timeMemory
56996RezwanArefin01Factories (JOI14_factories)C++14
33 / 100
8102 ms504180 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; typedef long long ll; const int MAX = 5e5 + 10; vector<int> adj[MAX], cost[MAX]; int lvl[MAX], sub[MAX], p[MAX], vis[MAX]; ll d[20][MAX], ans[MAX]; void calc(int u, int par) { sub[u] = 1; for(int v : adj[u]) if(v - par && !vis[v]) calc(v, u), sub[u] += sub[v]; } int centroid(int u, int par, int r) { for(int v : adj[u]) if(v - par && !vis[v]) if(sub[v] > r) return centroid(v, u, r); return u; } void dfs(int l, int u, int par, int pcost) { if(par + 1) d[l][u] = d[l][par] + pcost; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i], c = cost[u][i]; if(v == par || vis[v]) continue; dfs(l, v, u, c); } } void decompose(int u, int par) { calc(u, -1); int c = centroid(u, -1, sub[u] >> 1); vis[c] = 1, p[c] = par; if(par + 1) lvl[c] = lvl[par] + 1; dfs(lvl[c], c, -1, 0); for(int v : adj[c]) if(v - par && !vis[v]) decompose(v, c); } void update(int u) { for(int v = u; v + 1; v = p[v]) ans[v] = min(ans[v], d[lvl[v]][u]); } ll query(int u) { ll ret = 1e18; for(int v = u; v + 1; v = p[v]) ret = min(ret, ans[v] + d[lvl[v]][u]); return ret; } void Init(int N, int A[], int B[], int D[]) { for(int i = 0; i < N - 1; i++) { int u = A[i], v = B[i], c = D[i]; adj[u].push_back(v); adj[v].push_back(u); cost[u].push_back(c); cost[v].push_back(c); } for(int i = 0; i < N; i++) ans[i] = 1e18; decompose(0, -1); } long long Query(int S, int X[], int T, int Y[]) { for(int i = 0; i < S; i++) update(X[i]); ll ret = 1e18; for(int i = 0; i < T; i++) ret = min(ret, query(Y[i])); for(int i = 0; i < S; i++) { for(int v = X[i]; v + 1; v = p[v]) ans[v] = 1e18; } return ret; }

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...