제출 #1288024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288024		nguyenkhangninh99	Putovanje (COCI20_putovanje)	C++20	110 / 110	107 ms	32224 KiB

putovanje

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

const int maxn = 2e5 + 5;

vector<array<int, 3>> g[maxn];
int cost1[maxn], cost2[maxn], jump[maxn][20], h[maxn], cnt[maxn];

void dfs(int u, int p){
    for(auto [v, w1, w2]: g[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        jump[v][0] = u;
        cost1[v] = w1;
        cost2[v] = w2;
        dfs(v, u);
    }
}

int LCA(int u , int v){
    if(h[u] < h[v]) swap(u , v);

    for(int i = 19; i >= 0; i--) if(h[jump[u][i]] >= h[v]) u = jump[u][i];
    if(u == v) return u;

    for(int i = 19; i >= 0; i--){
        if(jump[u][i] != jump[v][i]) u = jump[u][i], v = jump[v][i];
    }
    return jump[u][0];
}

void add(int u , int p){
    for(auto [v, trash, _]: g[u]){
        if(v == p) continue;
        add(v , u);
        cnt[u] += cnt[v];
    }
}

void solve(){
    int n; cin >> n;
    for(int i = 1; i < n; i++){
        int u, v, w1, w2; cin >> u >> v >> w1 >> w2;
        g[u].push_back({v, w1, w2});
        g[v].push_back({u, w1, w2});
    }

    dfs(1, 1);
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++) jump[i][j] = jump[jump[i][j - 1]][j - 1];
    }

    for(int i = 1; i < n; i++){
        cnt[i]++; 
        cnt[i + 1]++;
        cnt[LCA(i, i + 1)] -= 2;
    }
    add(1, 1);

    int ans = 0;
    for(int i = 1; i <= n; i++) ans += min(cnt[i] * cost1[i], cost2[i]);
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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