Submission #1276786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276786		g4yuhg	Putovanje (COCI20_putovanje)	C++20	110 / 110	171 ms	53388 KiB

putovanje

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e9
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 200005
using namespace std;
map<ll, pii> mp[N];
struct Canh {
    ll u, v, c1, c2;
} canh[N];
ll n, par[N][LOG + 2], high[N], d[N];
pii cost[N];
vector<ll> adj[N];
void prepare() {
    high[0] = -1;
    for( int j = 1 ; j <= LOG ; j++ ){
        for( int i = 1 ; i <= n; i++ ){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    
}
ll lca(ll u, ll v){ // mac dinh u > v 
    if ( high[v] > high[u] ) return lca(v,u);
    
    for( int i = LOG ; i >= 0 ; i-- ) if( high[par[u][i]] >= high[v] ) {
        u = par[u][i];
    }
    if( u == v ) return v;
    //gd 2 ;
    for( int i = LOG ; i >= 0 ; i-- ){
        if( par[u][i] != par[v][i] ){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}
void dfs(ll u, ll parent) {
    for (auto v : adj[u]) {
        if (v == parent) continue;
        par[v][0] = u;
        high[v] = high[u] + 1;
        dfs(v, u);
    }
}
void dfs_cal(ll u, ll parent) {
    for (auto v : adj[u]) {
        if (v == parent) {
            continue;
        }
        dfs_cal(v, u);
        d[u] += d[v];
    }
}
signed main(void) {
    faster;
    cin >> n;
    for (int i = 1; i <= n - 1; i ++) {
        ll u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        adj[u].push_back(v);
        adj[v].push_back(u);
        mp[u][v] = mp[v][u] = {c1, c2};
        canh[i] = {u, v, c1, c2};
    }
    dfs(1, 1);
    prepare();
    for (int i = 1; i <= n - 1; i ++) {
        ll x = lca(i, i + 1);
        d[i] ++ ;
        d[i + 1] ++ ;
        d[x] -= 2;
    }
    dfs_cal(1, 1);
    ll ans = 0;
    for (int i = 2; i <= n; i ++) {
        ll c1 = mp[i][par[i][0]].fi, c2 = mp[i][par[i][0]].se;
        ans = ans + min(c1 * d[i], c2);
    }
    cout << ans;
    return 0;
}

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