제출 #113515

#제출 시각아이디문제언어결과실행 시간메모리
113515AngusRitossa공장들 (JOI14_factories)C++14
100 / 100
4891 ms225428 KiB
#include "factories.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define D(x...) printf(x) #else #define D(x...) #endif typedef long long ll; int n; vector<pair<int, int> > adj[500010]; int iscentroid[500010]; int sz[500010]; ll closest[500010]; pair<int, ll> mycentroids[500010][20]; int findsz(int a, int p = -1) { sz[a] = 1; for (auto b : adj[a]) { if (b.first != p && !iscentroid[b.first]) sz[a] += findsz(b.first, a); } return sz[a]; } ll len = 0; void dfslen(int a, int c, int p = -1, ll len = 0) { mycentroids[a][iscentroid[c]-1] = { c, len }; D("%d belongs to %d, dis %lld\n", a, c, len); for (auto b : adj[a]) { if (!iscentroid[b.first] && b.first != p) { dfslen(b.first, c, a, len+b.second); } } } void findcentroid(int a, int upto = 1, int above = 0, int p = -1) { int sumchildren = above+1; pair<int, int> mxchild = { 0, 0 }; for (auto b : adj[a]) { if (b.first != p && !iscentroid[b.first]) { mxchild = max(mxchild, { sz[b.first], b.first } ); sumchildren += sz[b.first]; } } if (mxchild.first <= (sumchildren)/2) { // is a centroid iscentroid[a] = upto; dfslen(a, a); if (p != -1 && !iscentroid[p]) findsz(p, a); for (auto b : adj[a]) { if (!iscentroid[b.first]) findcentroid(b.first, upto+1); } return; } findcentroid(mxchild.second, upto, sumchildren-mxchild.first, a); } void Init(int N, int A[], int B[], int D[]) { n = N; for (int i = 0; i < n-1; i++) { adj[A[i]].emplace_back(B[i], D[i]); adj[B[i]].emplace_back(A[i], D[i]); } for (int i = 0; i < n; i++) fill_n(mycentroids[i], 20, make_pair(0, 1e15)); findsz(0); findcentroid(0); fill_n(closest, n, 1e15); } ll Query(int s, int x[], int t, int y[]) { ll ans = 1e15; for (int i = 0; i < s; i++) for (int j = 0; j < 20; j++) { auto c = mycentroids[x[i]][j]; closest[c.first] = min(closest[c.first], c.second); } for (int i = 0; i < t; i++) for (int j = 0; j < 20; j++) { auto c = mycentroids[y[i]][j]; ans = min(ans, closest[c.first]+c.second); } for (int i = 0; i < s; i++) for (int j = 0; j < 20; j++) { auto c = mycentroids[x[i]][j]; closest[c.first] = 1e15; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...