제출 #212578

#제출 시각아이디문제언어결과실행 시간메모리
212578ChrisT공장들 (JOI14_factories)C++17
100 / 100
5098 ms509532 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair<int,int>; using pll = pair<ll,ll>; using pil = pair<int,ll>; using ld = long double; #define all(x) (x).begin(),(x).end() const int MN = 5e5+3, LOG = 20, MOD = 1e9+7; mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count()); int sz[MN], p[MN], st[MN], tt=0; bool done[MN]; ll push[MN], down[MN], up[MN], sp[MN<<1][LOG]; vector<pii> adj[MN];vector<pil> go[MN]; void prep (int cur, int par = -1) { sp[st[cur] = ++tt][0] = push[cur]; for (pii i : adj[cur]) if (i.first != par) { push[i.first] = push[cur] + i.second; prep(i.first,cur); sp[++tt][0] = push[cur]; } } void initlca () { for (int j = 1; j < LOG; j++) for (int i = 1; i <= tt-(1<<j)+1; i++) sp[i][j] = min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]); } ll dist (int a, int b) { if (a == b) return 0; if (st[a] > st[b]) swap(a,b); int lg = 31 - __builtin_clz(st[b]-st[a]+1); return push[a] + push[b] - min(sp[st[a]][lg],sp[st[b]-(1<<lg)+1][lg])*2; } int dfs (int cur, int par = -1) { sz[cur] = 1; for (pii i : adj[cur]) if (!done[i.first] && i.first != par) { sz[cur] += dfs(i.first,cur); } return sz[cur]; } int findcent (int cur, int tot, int par = -1) { for (pii i : adj[cur]) { if (i.first != par && !done[i.first] && sz[i.first] > (tot>>1)) return findcent(i.first,tot,cur); } return cur; } void maketree (int cur, int lst = 0) { dfs(cur); int cent = findcent(cur,sz[cur]); done[cent] = 1; p[cent] = lst; for (pii i : adj[cent]) if (!done[i.first]) maketree(i.first,cent); } void Init (int n, int *a, int *b, int *d) { 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]); } prep(1); maketree(1); initlca(); for (int i = 1; i <= n; i++) { int cur = i; while (cur) { go[i].emplace_back(cur,dist(i,cur)); cur = p[cur]; } } memset(down,0x3f,sizeof down); } ll Query (int s, int *x, int t, int *y) { ll ret = LLONG_MAX; for (int i = 0; i < s; i++) { for (auto &pp : go[++x[i]]) if (pp.second < down[pp.first]) down[pp.first] = pp.second; } for (int i = 0; i < t; i++) { for (auto &pp : go[++y[i]]) ret = min(ret,pp.second + down[pp.first]); } for (int i = 0; i < s; i++) { for (auto &pp : go[x[i]]) down[pp.first] = 1e18; } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...