제출 #1112813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112813		ezzzay	Putovanje (COCI20_putovanje)	C++14	110 / 110	165 ms	40520 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<pair<int,pair<int,int> > >v [N] ;
int ans=0;
int dp[N];
int par[32][N];
int sbtr[N];
int dist[N];
void dfs(int a, int p){
    for(auto k:v[a]){
        int b= k.ff;
        if(b==p)continue;
        par[0][b]=a;
         dist[b]=dist[a]+1;
        dfs(b,a);
    }
}
int lca(int a, int b){
    if(dist[b]>dist[a])swap(a,b);
    int x=dist[a]-dist[b];
    for(int i=0;i<=18;i++){
        if(x & (1<<i)){
            a=par[i][a];
        }
    }
    x=0;
    int u=a,g=b;
    if(a==b){
        return a;
    }
    for(int i=25;i>=0;i--){
        if(par[i][u]!=par[i][g]){
            u=par[i][u];
            g=par[i][g];
        }
    }
    u=par[0][u];
    return u;
}
void fun(int a, int p){
    for(auto k:v[a]){
        int b=k.ff;
        int c1=k.ss.ff,c2=k.ss.ss;
        
        if(b==p)continue;
        fun(b,a);
        ans+=min(c1*sbtr[b],c2);
        sbtr[a]+=sbtr[b];
    }
    sbtr[a]+=dp[a];
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c1,c2;
        cin>>a>>b>>c1>>c2;
        v[a].pb({b,{c1,c2}});
        v[b].pb({a,{c1,c2}});
    }
    par[0][1]=1;
    dfs(1,0);
    for(int i=1;i<19;i++){
        for(int j=1;j<=n;j++){
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
    for(int i=1;i<n;i++){
        int a=i,b=i+1;
        dp[a]++;
        dp[b]++;
        int c=lca(a,b);
        dp[c]-=2;
    }
    
    fun(1,0);
    
    cout<<ans;
}

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