제출 #203219

#제출 시각아이디문제언어결과실행 시간메모리
203219mayhoubsalehPolitičari (COCI20_politicari)C++14
0 / 70
456 ms524292 KiB
#include <bits/stdc++.h> #define pb push_back #define ll long long #define left 2*i+1 #define righ 2*i+2 #define mid (l+r)/2 using namespace std; ll n,m; const ll mxs=200005; vector<ll>v[mxs],tr; ll e[mxs][4]; ll par[mxs],lazy[mxs],head[mxs],heavy[mxs],dep[mxs],st[4*mxs],id[mxs]; ll dfs(ll nod,ll fat){ par[nod]=fat; dep[nod]=1+dep[fat]; ll sz=1; ll mx=-1; for(auto x:v[nod]){ if(x==fat)continue; ll cursz=dfs(x,nod); sz+=cursz; if(cursz>mx){ heavy[nod]=x; mx=cursz; } } return sz; } void dec(ll nod,ll h){ id[nod]=tr.size(); tr.pb(nod); head[nod]=h; if(heavy[nod])dec(heavy[nod],h); for(auto x:v[nod]){ if(x==heavy[nod]||x==par[nod])continue; dec(x,x); } } void frt(ll i,ll l,ll r){ if(lazy[i]){ st[i]+=(r-l+1)*lazy[i]; if(l!=r){ lazy[left]+=lazy[i]; lazy[righ]+=lazy[i]; } lazy[i]=0; } } ll getans(ll i,ll l,ll r,ll id){ frt(i,l,r); if(r<id||l>id)return 0; if(l==r)return st[i]; return getans(left,l,mid,id)+getans(righ,mid+1,r,id); } void upd(ll i,ll l,ll r,ll ql,ll qr){ frt(i,l,r); if(r<ql||l>qr)return; if(l>=ql&&r<=qr){ st[i]+=(r-l+1); if(l!=r){ lazy[left]++; lazy[righ]++; } return ; } upd(left,l,mid,ql,qr); upd(righ,mid+1,r,ql,qr); st[i]=st[left]+st[righ]; } void add(ll x,ll y){ while(head[x]!=head[y]){ if(dep[head[x]]<dep[head[y]])swap(x,y); upd(0,0,m-1,id[head[x]],id[x]); x=par[head[x]]; } if(x==y)return; if(id[x]>id[y])swap(x,y); upd(0,0,m-1,id[x]+1,id[y]); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(ll i=0;i<n-1;i++){ for(ll j=0;j<4;j++){ cin>>e[i][j]; } v[e[i][0]].pb(e[i][1]); v[e[i][1]].pb(e[i][0]); } dfs(1,0); dec(1,1); m=tr.size(); for(ll i=1;i<n;i++){ add(i,i+1); } //for(ll i=1;i<=n;i++)cout<<i<<' '<<head[i],cout<<endl; ll ans=0; for(ll i=0;i<n-1;i++){ if(e[i][0]==par[e[i][1]])swap(e[i][0],e[i][1]); ll cnt=getans(0,0,m-1,id[e[i][0]]); //cout<<cnt<<endl; ans+=min(cnt*e[i][2],e[i][3]); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...