Submission #203222

#	Time	Username	Problem	Language	Result	Execution time	Memory
203222		mayhoubsaleh	Političari (COCI20_politicari)	C++14	0 / 70	502 ms	524292 KiB

politicari

#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=210005;
vector<ll>v[mxs],tr;
ll e[mxs][4];
ll par[mxs],lazy[4*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;
}

• Subtask 1: 0 / 70