제출 #201767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201767		EmmanuelAC	Putovanje (COCI20_putovanje)	C++14	110 / 110	477 ms	48784 KiB

putovanje

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

struct nd{
    vector<ll> ady;
}T[200010];

ll n,u,v,a,b,d[200010],f[200010][20],sum[200010],ans;
map< pll , pll > c;

void dfs(ll node,ll ant,ll dist){
    d[ node ] = dist;
    f[ node ][ 0 ] = ant;
    for(auto sig:T[node].ady){
        if( sig==ant ) continue;
        dfs( sig , node , dist+1 );
    }
    return;
}

ll lca( ll A , ll B ){
    if( d[ A ] < d[ B ] ) swap( A , B );
    for(int i=19; i>=0; i--) if( d[A]-(1LL<<i) >= d[ B ] ){
        A = f[ A ][ i ];
    }
    if( A==B ) return B;
    for(int i=19; i>=0; i--){
        if( f[A][i]!=f[B][i] ){
            A = f[A][i];
            B = f[B][i];
        }
    }

    return f[A][0];
}

void compute(ll node, ll ant){
    for(auto sig:T[node].ady){
        if( sig == ant ) continue;
        compute( sig , node );
        sum[node]+=sum[sig];
    }

    if( node!=1 ) ans+=min( sum[node]*c[ { node , ant } ].fi , c[ { node , ant } ].se );
    return;
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<n; i++){
        cin >> u >> v >> a >> b;
        c[ {u,v} ] = c[ {v,u} ] = {a,b};
        T[u].ady.pb( v );
        T[v].ady.pb( u );
    }

    dfs( 1  , 1 , 0 );

    for(int pot=1; pot<20; pot++) for(int i=1; i<=n; i++) f[i][pot] = f[ f[i][pot-1] ][ pot-1 ];

    for(int i=1; i<n; i++){
        sum[i]++;
        sum[i+1]++;
        sum[ lca( i , i+1 ) ]-=2;
    }

    compute( 1 , 1 );

    cout << ans;

    return 0;
}

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