제출 #857800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857800		trieghv	Putovanje (COCI20_putovanje)	C++14	110 / 110	104 ms	63452 KiB

putovanje

/* Author : Do Thanh Triet - Tran Hung Dao High School for Gifted Student */
/*      Algorithms + Data structures + Arts programming = Program <3      */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ft first
#define sc second
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define all(x) x.begin(), x.end()

#define ON_BIT(mask, i) ((mask) | (1LL << i))
#define OFF_BIT(mask, i) ((mask) & ~(1LL << i))
#define C_BIT(mask) __builtin_popcountll(mask)
#define BIT(mask, i) ((mask) & (1LL << i))
#define F1BIT(mask) __builtin_ffsll(mask)
#define endl '\n'
#define int ll

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 9;
const int N =  2e5 + 9;
const int MOD = 1e9 + 7;
const long long INF = 0x3f;
const long long oo = 1e18 +  9;

#define TASK "code"

int n;
ii cost[maxn];
vector<ii>adj[maxn];

int h[maxn], p[maxn][21];
int t[maxn], dp[maxn];

int cnt[maxn];

void predfs(int u, int par) {
    for (ii &x : adj[u]) {
        int v = x.ft;
        if (v == par) continue;
        h[v] = h[u] + 1;
        p[v][0] = u;
        for (int j = 1; (1<<j) <= n; ++j) p[v][j] = p[p[v][j - 1]][j - 1];
        predfs(v, u);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int log = log2(h[u]);
    FORD(i, log, 0) {
        if (h[u] - (1<<i) >= h[v]) {
            u = p[u][i];
        }
    }
    if (u == v) return u;
    FORD(i, log, 0) {
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

void dfs_cal(int u, int par, int pos) {
    for (ii &x : adj[u]) {
        int v = x.ft, id = x.sc;
        if (v == par) continue;
        dfs_cal(v, u, id);
        dp[u] += dp[v];
    }
    dp[u] += t[u];
    if (pos != -1) cnt[pos] = dp[u];
}

void solve() {
    cin >> n;
    FOR(i, 1, n - 1) {
        int u, v, id;
        id = i;
        cin >> u >> v >> cost[id].ft >> cost[id].sc;
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
    }
    predfs(1, 0);
    FOR(i,1,n - 1) {
        t[i]++;
        t[i + 1]++;
        t[lca(i, i + 1)] -=2;
    }

    dfs_cal(1, 0, -1);

    int res = 0;
    FOR(i, 1, n - 1) {
        res += min(cost[i].ft * cnt[i], cost[i].sc);
    }
    cout<<res;
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen(TASK ".inp", "r", stdin);
    //freopen(TASK ".out", "w", stdout);
    solve();
    return 0;
}
//Take a deep breath, don't be nervous, read the question slowly and understand the question, the question is often simpler than you think.
/*
Input:

*/
/*
Output:

*/

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