제출 #74288

#제출 시각아이디문제언어결과실행 시간메모리
74288kingpig9공장들 (JOI14_factories)C++11
0 / 100
18 ms12408 KiB
#include <bits/stdc++.h> #include "factories.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define debug(...) fprintf(stderr, __VA_ARGS__) //#define debug(...) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) const int MAXN = 5e5 + 10; const int MAXLG = 19; const ll INF = 1e16; void setmin (ll &a, ll b) { if (a > b) { a = b; } } int N; vector<pll> adj[MAXN]; ll ans[MAXN]; int sz[MAXN]; bool vis[MAXN]; int dfssz (int x, int p) { sz[x] = 1; for (auto py : adj[x]) { int y = py.fi; if (y != p && !vis[y]) { sz[x] += dfssz(y, x); } } return sz[x]; } int findcent (int x, int p, int s) { for (auto py : adj[x]) { int y = py.fi; if (y != p && !vis[y]) { return findcent(y, x, s); } } return x; } int par[MAXN]; int hcent[MAXN]; ll dist[20][MAXN]; //Note: here, you are not actually dfsing through centroid tree - you are dfsing through the original tree. void dfslow (int x, int p, int h, ll w) { dist[h][x] = w; for (pll py : adj[x]) { int y = py.fi; if (y != p && !vis[y]) { dfslow(y, x, h, w + py.se); } } } void dfsc (int x, int pc) { int szcmp = dfssz(x, -1); exit(0); x = findcent(x, -1, szcmp); vis[x] = true; par[x] = pc; if (pc != -1) { hcent[x] = hcent[pc] + 1; } dfslow(x, -1, hcent[x], 0ll); //dfs to unvisited vertices - or "low" vertices (in the subtree). for (auto py : adj[x]) { int y = py.fi; if (y != pc && !vis[y]) { dfsc(y, x); } } } void update (int x, bool reset) { for (int i = x; i != -1; i = par[i]) { if (reset) { ans[i] = INF; } else { setmin(ans[i], dist[hcent[i]][x]); } } } ll query (int x) { ll res = INF; for (int i = x; i != -1; i = par[i]) { setmin(res, ans[i] + dist[hcent[i]][x]); } return res; } void Init (int nn, int a[], int b[], int d[]) { N = nn; for (int i = 0; i < N - 1; i++) { adj[a[i]].push_back(pll(b[i], d[i])); adj[b[i]].push_back(pll(a[i], d[i])); } for (int i = 0; i < N; i++) { ans[i] = INF; } dfsc(0, -1); } ll Query (int S, int X[], int T, int Y[]) { for (int i = 0; i < S; i++) { update(X[i], false); } ll ans = INF; for (int i = 0; i < T; i++) { setmin(ans, query(Y[i])); } for (int i = 0; i < S; i++) { update(X[i], true); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...