Submission #915739

#TimeUsernameProblemLanguageResultExecution timeMemory
915739KiaRezConstruction of Highway (JOI18_construction)C++17
100 / 100
236 ms32148 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 2e5+23, lg = 18; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, a[N], b[N], c[N], h[N], par[N], head[N], subt[N], fen[N]; int tim, tin[N], tout[N]; vector<int> comp, adj[N]; vector<pll> g[N], rbk; void upd(int ind, int val) { if(ind == 0) return; rbk.pb({ind, val}); while(ind < N) { fen[ind] += val; ind += (ind&(-ind)); } } void rolbak() { while(size(rbk) > 0) { upd(rbk.back().F, -rbk.back().S); rbk.pop_back(); rbk.pop_back(); } } int qry(int ind) { int res = 0; while(ind > 0) { res += fen[ind]; ind -= (ind&(-ind)); } return res; } void init(int v, int p=0) { par[v] = p, subt[v] = 1, h[v] = h[p] + 1; for(int u : adj[v]) { if(u == p) continue; init(u, v); subt[v] += subt[u]; } } void dfs(int v, int p) { head[v] = p, tin[v] = ++tim; int mx = 0; for(int u : adj[v]) { if(u == par[v]) continue; mx = (subt[mx]>subt[u] ? mx : u); } for(int u : adj[v]) { if(u==par[v] || u==mx) continue; dfs(u, u); } if(mx != 0) dfs(mx, p); tout[v] = tim+1; } ll query(ll v) { if(v == 0) return 0; ll res = 0, u = head[v], num = h[v]-h[head[v]]+1; vector<pll> tmp; for(int i=size(g[u])-1; num>0&&i>=0; i--) { tmp.pb({g[u][i].F, min(g[u][i].S, num)}); num -= min(g[u][i].S, num); } reverse(all(tmp)); for(auto it : tmp) { res += (it.S*qry(it.F-1)); upd(it.F, it.S); } return res+query(par[u]); } void update(int v, ll val, int flg=0) { if(v == 0) return; if(flg == 1) { g[head[v]].clear(); g[head[v]].pb({val, h[v]-h[head[v]]+1}); update(par[head[v]], val); return; } ll u = head[v], num = h[v]-h[head[v]]+1; while(size(g[u])>0 && num>0) { if(num>=g[u].back().S) { num -= g[u].back().S; g[u].pop_back(); } else { g[u].back().S -= num; num=0; } } g[u].pb({val, h[v]-h[u]+1}); update(par[u], val); } int main () { ios_base::sync_with_stdio(false), cin.tie(0); cin>>n; for(int i=1; i<=n; i++) { cin>>c[i]; comp.pb(c[i]); } sort(all(comp)); comp.resize(unique(all(comp)) - comp.begin()); for(int i=1; i<=n; i++) { c[i] = lower_bound(all(comp), c[i]) - comp.begin() + 1; } vector<pii> Q; for(int v,u,i=1; i<n; i++) { cin>>v>>u; adj[v].pb(u); adj[u].pb(v); Q.pb({v, u}); } init(1); dfs(1, 1); g[1].pb({c[1], 1}); for(auto it : Q) { if(h[it.F] > h[it.S]) swap(it.F, it.S); cout<<query(it.F)<<endl; update(it.S, c[it.S], 1); rolbak(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...