Submission #1014694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014694		soumil69	Putovanje (COCI20_putovanje)	C++17	110 / 110	186 ms	33204 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;

#define ve vector
#define ll long long

int n,tim,nume,sz;
ve<ve<pair<int,int> > > adj;
ve<int> lete,rite,tin,tout;
ve<ll> seg;
ve<ll> sinc,mulc;
ve<ve<int> > pars;
ve<int> dist;
ve<ll> cost;
int M=20;

void dfs(int cur,int par){
    int sz=adj[cur].size();
    pars[cur].resize(M,-1);
    pars[cur][0]=par;
    for(int i=1;i<M;i++){
        int pr=pars[cur][i-1];
        if(pr==-1){
            break;
        }
        pars[cur][i]=pars[pr][i-1];
    }
    tin[cur]=tim;
    for(int i=0;i<sz;i++){
        if(adj[cur][i].first==par){
            continue;
        }
        dist[adj[cur][i].first]=dist[cur]+1;
        lete[adj[cur][i].second]=tim++;
        dfs(adj[cur][i].first,cur);
        rite[adj[cur][i].second]=tim++;
    }
    tout[cur]=tim;
}

int up(int a,int k){
    int i=0;
    while(k){
        if(k&1){
            a=pars[a][i];
        }
        i++;
        k>>=1;
    }
    return a;
}

int lca(int a,int b){
    if(dist[a]>dist[b]){
        swap(a,b);
    }
    int upp=dist[b]-dist[a];
    if(upp){
        b=up(b,upp);
    }
    int k=M-1;
    while(a!=b && k>=0){
        int a1=pars[a][k],b1=pars[b][k];
        if(a1!=b1){
            a=a1,b=b1;
        }
        k--;
    }
    if(a!=b){
        return pars[a][0];
    }
    return a;
}

void supd(int l,int val){
    l+=sz;
    while(l){
        seg[l]+=val;
        l=l>>1;
    }
}

void upd(int a,int b){
    int anc=lca(a,b);
    supd(tin[anc],2);
    if(tout[a]<sz)supd(tout[a],-1);
    if(tout[b]<sz)supd(tout[b],-1);
}

int query(int i){
    int l=sz,r=i+sz,sm=0;
    while(r>l){
        if(r&1){
            sm+=seg[--r];
        }
        if(l&1){
            sm+=seg[l++];
        }
        l>>=1,r>>=1;
    }
    return sm;
}

int main(){
   cin>>n;
   nume=n-1,tim=0;
   adj.resize(n);
   lete.resize(nume);
   rite.resize(nume);
   seg.resize(4*nume+2);
   tin.resize(n);
   tout.resize(n);
   sinc.resize(nume);
   mulc.resize(nume);
   pars.resize(n);
   dist.resize(n,0);
   for(int i=0;i<n-1;i++){
       int a,b;
       ll sc,mc;
       cin>>a>>b>>sc>>mc;
       a--,b--;
       adj[a].push_back({b,i});
       adj[b].push_back({a,i});
       sinc[i]=sc,mulc[i]=mc;
   }
   dfs(0,-1);
   sz=(nume<<1);
//   cos.resize(sz);
//   for(int i=0;i<nume;i++){
//       cout<<"edge "<<i+1<<" "<<lete[i]<<" "<<rite[i]<<endl;
//   }
   ll ans=0;
   for(int i=0;i<n-1;i++){
       upd(i,i+1);
   }
//   for(int i=0;i<seg.size();i++){
//       cout<<seg[i]<<' ';
//   }
//   cout<<endl;
   for(int i=0;i<nume;i++){
       int times=query(lete[i]+1)-query(rite[i]+1);
       if((ll)times*sinc[i]>=mulc[i]){
           ans+=mulc[i];
       }
       else{
           ans+=(ll)times*sinc[i];
       }
   }
   cout<<ans<<endl;
    
    return 0;
}

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