| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 658882 | esomer | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>#include "factories.h"using namespace std;#define ll long long#define endl "\n"const int MOD = 998244353;const int maxN = 500001;const int maxEuler = 3000000;const int maxlog = 20;int sparse[maxEuler][23];int euler[maxEuler];int lb[maxEuler];pair<int, int> t[maxN];ll dists[maxN];int depths[maxN];vector<pair<int, ll>> adj[maxN];bool done[maxN];int subtree_size[maxN];int parents[maxN];ll ans[maxN];int centr;int cnt;void DFS_lca(int x, int p){ t[x].first = cnt; euler[cnt] = x; cnt++; for(auto pr : adj[x]){ int node = pr.first; if(node != p){ depths[node] = depths[x] + 1; dists[node] = dists[x] + pr.second; DFS_lca(node, x); t[x].second = cnt; euler[cnt] = x; cnt++; } } if(t[x].first + 1 == cnt){ t[x].second = cnt; euler[cnt] = x; cnt++; }}void build_lca(int n){ depths[0] = 0; dists[0] = 0; cnt = 0; DFS_lca(0, -1); for(int i = 0; i < 23; i++){ for(int j = 0; j < cnt; j++){ if(i > 0){ if(depths[sparse[j][i - 1]] < depths[sparse[max(0, j - (1<<(i - 1)))][i - 1]]){ sparse[j][i] = sparse[j][i - 1]; }else sparse[j][i] = sparse[max(0, j - (1<<(i - 1)))][i - 1]; } else sparse[j][i] = euler[j]; } } ll pw = 1; int curr = 0; for(int i = 1; i <= cnt; i++){ if(i == pw * 2){ pw *= 2; curr++; } lb[i] = curr; }}int lca(int a, int b){ if(a == b) return a; int l = min(t[a].first, t[b].first); int r = max(t[a].second, t[b].second); int dst = r - l + 1; if(depths[sparse[r][lb[dst]]] < depths[sparse[l + (1 << lb[dst]) - 1][lb[dst]]]) return sparse[r][lb[dst]]; else return sparse[l + (1 << lb[dst]) - 1][lb[dst]];}ll dist(int a, int b){ int anc = lca(a, b); return dists[a] + dists[b] - 2 * dists[anc];}int find_size(int x, int par){ subtree_size[x] = 1; for(auto pr : adj[x]){ int node = pr.first; if(node == par || done[node] == 1) continue; subtree_size[x] += find_size(node, x); } return subtree_size[x];}void find_centroid(int x, int par, int siz){ bool good = 1; for(auto pr : adj[x]){ int node = pr.first; if(node == par || done[node] == 1) continue; if(subtree_size[node] > siz / 2){ find_centroid(node, x, siz); good = 0; } } if(good) centr = x;}void build(int x, int par){ int siz = find_size(x, -1); centr = -1; find_centroid(x, -1, siz); parents[centr] = par; done[centr] = 1; for(auto pr : adj[centr]){ int node = pr.first; if(!done[node]) build(node, centr); }}void add(int x){ int next = x; while(next != -1){ ll d = dist(next, x); ans[next] = min(ans[next], d); next = parents[next]; }}void rmv(int x){ int next = x; while(next != -1){ ans[next] = 1e18; next = parents[next]; }}ll query(int x){ int next = x; ll rep = 1e18; while(next != -1){ ll d = dist(next, x); rep = min(rep, ans[next] + d); next = parents[next]; } return rep;}void Init(int N, int A[], int B[], int D[]){ for(int i = 0; i < N - 1; i++){ adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } build_lca(N); build(0, -1); for(int i = 0; i < N; i++) ans[i] = 1e18;}ll Query(int S, int X[], int T, int Y[]){ for(int i = 0; i < S; i++) add(X[i]); ll retrn = 1e18; for(int i = 0; i < T; i++) retrn = min(retrn, query(Y[i])); for(int i = 0; i < S; i++) rmv(X[i]); return retrn;}