제출 #878481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878481		LePhiPhat	Putovanje (COCI20_putovanje)	C++17	25 / 110	324 ms	63180 KiB

putovanje

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debuge.cpp"
#else
#define debug(...) 42;
#endif

using namespace std;

using ii = pair<int, int>;
using ll = long long;
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int N = 200001;
vector<int> g[N];
ll dep[N], up[N][20], dp[N];
void dfs(int u, int p) {
    up[u][0] = p;
    for (int &v: g[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}
void calc(int n) {
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
}
int jmp(int u, int k) {
    for (int i = 20; i >= 0; i--) {
        if ((k & (1ll << i))) {
            // debug(i, u, k, up[u][k]);
            u = up[u][i];
            // k -= (1ll << i);
        }
    }
    // debug("jmp", u);
    return u;
}
int lca(int u, int v) {
    // debug(u, v);
    if (dep[u] != dep[v]) {
        if (dep[u] < dep[v]) 
            swap(u, v);
        // debug(u, v);
        u = jmp(u, dep[u] - dep[v]);
    }
    // debug(u, v);
    if (u == v) return u;
    for (int i = 20; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}
void push(int u, int p) {
    for (int &v: g[u]) if (v != p) {
        push(v, u);
        dp[u] += dp[v];
    }
}
ll ans = 0;
map<pair<int, int>, ll> mp1, mp2;
void dfsAns(int u, int p) {
    for (auto &v: g[u]) if (v != p) {
        // debug(v, dp[v]);
        ans += min(mp1[{u, v}] * dp[v], mp2[{u, v}]) * 1ll;
        // ll calc = min(mp1[{u, v}] * dp[v], mp2[{u, v}]) * 1ll;
        // debug(u, v, calc);
        dfsAns(v, u);
    }
}
void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        ll u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        mp1[{u, v}] = c1;
        mp1[{v, u}] = c1;
        mp2[{u, v}] = c2;
        mp2[{v, u}] = c2;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for (int i = 1; i <= n; i++) {
    //     cout << "i: = " << i << " ";
    //     for (auto &j: g[i]) {
    //         cout << j << ' ';
    //     }
    //     cout << "\n";
    // }
    dfs(1, 1);
    calc(n);
    for (int i = 1; i < n; i++) {
        int u = i, v = i + 1;
        int LCA = lca(u, v);
        dp[LCA] -= 2; 
        dp[u]++;
        dp[v]++;
        // debug(u, v, LCA);
        // for (int j = 1; j <= n; j++) cout << dp[j] << " \n"[j == n];
    }  
    // for (int i = 1; i <= n; i++) {
    //     debug(i, dp[i]);
    // }
    push(1, 1);   
    dfsAns(1, 1);
    cout << ans;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    #ifdef LOCAL
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    #endif
    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
}

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