Submission #933339

#TimeUsernameProblemLanguageResultExecution timeMemory
933339parlimoosConstruction of Highway (JOI18_construction)C++14
100 / 100
500 ms34260 KiB
//Be Name KHODA #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pp pop_back #define lb lower_bound #define ub upper_bound #define cl clear #define bg begin #define arr(x) array<int , x> #define endl '\n' int n; vector<int> a , cmp; int tms[100000] , cs[100000] , hs[100000]; int pth[100000] , bl[100000][20]; int seg[400001][2] , seginf[400001][2] , is[100000]; int fen[100001]; int segcnt = 0; vector<int> tr[100000]; vector<arr(2)> ops; vector<arr(2)> ns; int timer = -1; void dfs1(int v = 0 , int p = -1){ cs[v] = 1 , bl[v][0] = p; if(p != -1) hs[v] = hs[p] + 1; for(int i = 1 ; i < 20 ; i++){ if(bl[v][i - 1] == -1) bl[v][i] = -1; else bl[v][i] = bl[bl[v][i - 1]][i - 1]; } for(int u : tr[v]) if(u != p) dfs1(u , v) , cs[v] += cs[u]; } void hld(int v = 0){ tms[v] = ++timer; int mxi = -1; for(int u : tr[v]) if(u != bl[v][0] and (mxi == -1 or cs[mxi] < cs[u])) mxi = u; if(mxi == -1) return; pth[mxi] = pth[v] , hld(mxi); for(int u : tr[v]) if(u != bl[v][0] and u != mxi) pth[u] = u , hld(u); } void buildSeg(int l = 0 , int r = n - 1 , int i = 1){ seginf[i][0] = l , seginf[i][1] = r , seg[i][1] = -1; if(l == r) is[l] = i; else{ int c = (r + l - 1) >> 1; buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1); } } void updSeg(int l , int r , int i , int val){ if(seginf[i][0] >= l and seginf[i][1] <= r) seg[i][0] = val , seg[i][1] = segcnt; else if(seginf[i][1] >= l and seginf[i][0] <= r) updSeg(l , r , i << 1 , val) , updSeg(l , r , (i << 1) | 1 , val); } arr(2) getSeg(int v){ int i = is[tms[v]] , res = seg[i][0] , time = seg[i][1]; while(i > 1){ i >>= 1; if(time < seg[i][1]) time = seg[i][1] , res = seg[i][0]; } return {res , time}; } void cmpInt(){ cmp = a; sort(cmp.bg() , cmp.end()); cmp.resize(int(unique(cmp.bg() , cmp.end()) - cmp.bg())); for(int &el : a) el = int(lb(cmp.bg() , cmp.end() , el) - cmp.bg()); } void addFen(int i , int val){ i++; while(i < n + 1) fen[i] += val , i += (i & (-i)); } int getFen(int l , int r){ int res = 0; r++; while(r > 0) res += fen[r] , r -= (r & (-r)); while(l > 0) res -= fen[l] , l -= (l & (-l)); return res; } void updPth(int v , int val){ while(v != -1){ updSeg(tms[pth[v]] , tms[v] , 1 , val); v = bl[pth[v]][0]; } segcnt++; } ll getPth(int v){ ns.cl(); ll res = 0; while(v != -1){ auto d = getSeg(v); int u = v; for(int i = 19 ; i >= 0 ; i--){ if(bl[u][i] == -1) continue; if(getSeg(bl[u][i]) == d) u = bl[u][i]; } ns.pb({d[0] , hs[v] - hs[u] + 1}); v = bl[u][0]; } for(int i = 0 ; i < (int)ns.size() ; i++){ if(ns[i][0] > 0) res += (1ll * ns[i][1]) * (1ll * getFen(0 , ns[i][0] - 1)); addFen(ns[i][0] , ns[i][1]); } for(int i = 0 ; i < (int)ns.size() ; i++) addFen(ns[i][0] , -(ns[i][1])); return res; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0 ; i < n ; i++){ int d; cin >> d; a.pb(d); } for(int i = 1 ; i < n ; i++){ int v , u; cin >> v >> u; v-- , u--; tr[v].pb(u) , tr[u].pb(v); ops.pb({v , u}); } dfs1() , hld() , cmpInt() , buildSeg(); for(auto op : ops){ ll o = getPth(op[0]); cout << o << endl; updPth(op[1] , a[op[1]]); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...