제출 #203683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
203683		mayhoubsaleh	Putovanje (COCI20_putovanje)	C++14	110 / 110	336 ms	25336 KiB

putovanje

#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,cnt;ll ans;
const ll mxs=2e5+1000;
ll dep[mxs],head[mxs],ed[mxs][4],lazy[4*mxs],st[4*mxs],par[mxs];
vector<ll>v[mxs];
ll heavy[mxs];
ll dfs(ll nod,ll fat){
    par[nod]=fat;
    dep[nod]=1+dep[fat];
    ll mx=-1;
    ll sz=1;
    for(auto x:v[nod]){
        if(x==fat)continue;
        ll cursz=dfs(x,nod);
        sz+=cursz;
        if(cursz>mx){
            mx=cursz;
            heavy[nod]=x;
        }
    }
    return sz;
}

ll pos[mxs];

void dec(ll nod,ll h){
    pos[nod]=cnt++;
    head[nod]=h;
    if(heavy[nod]){
        dec(heavy[nod],h);
    }
    for(auto x:v[nod]){
        if(x==par[nod]||x==heavy[nod])continue;
        dec(x,x);
    }
}

inline 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,cnt-1,pos[head[x]],pos[x]);
        x=par[head[x]];
    }
    if(x==y)return;
    if(pos[x]>pos[y])swap(x,y);
    x=heavy[x];
    upd(0,0,cnt-1,pos[x],pos[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>>ed[i][j];
        v[ed[i][0]].pb(ed[i][1]);
        v[ed[i][1]].pb(ed[i][0]);
    }

    dfs(1,0);
    dec(1,1);

    /*for(int i=1;i<=n;i++){
        cout<<pos[i]<<' '<<endl;
    }*/
    for(ll i=1;i<n;i++){
        add(i,i+1);
    }


    for(ll i=0;i<n-1;i++){
        if(ed[i][0]==par[ed[i][1]])swap(ed[i][0],ed[i][1]);
        ll cur=getans(0,0,cnt-1,pos[ed[i][0]]);
        //cout<<ed[i][0]<<' '<<ed[i][1]<<' '<<cur<<endl;
        ans+=min(cur*ed[i][2],ed[i][3]);
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65