Submission #957627

#	Time	Username	Problem	Language	Result	Execution time	Memory
957627		vjudge1	Putovanje (COCI20_putovanje)	C++17	110 / 110	251 ms	49884 KiB

putovanje

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

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

#define int ll
#define pb push_back
#define ll long long
#define i2 array<int, 2>
#define SZ(x) (int) (x).size()

const int N = 2e5 + 4, LG = 20;

int n, h[N], pos[N], neg[N], cnt[N], anc[N][LG];
vector<int> adj[N];
map<i2, i2> cost;

void dfs(int v = 1, int p = 1) {
    for (int i = 1; i < LG; i++) {
        int u = anc[v][i - 1];
        u = anc[u][i - 1];
        if (u)
            anc[v][i] = u;
    }
    for (int u : adj[v]) {
        if (u != p) {
            anc[u][0] = v;
            h[u] = h[v] + 1;
            dfs(u, v);
        }
    }
}

int up(int v, int k) {
    for (int i = 0; i < LG; i++) {
        if ((1 << i) & k) 
            v = anc[v][i];
        if (!v)
            break;
    }    
    return v;
}

int lca(int v, int u) {
    if (h[v] < h[u]) 
        swap(v, u);
    v = up(v, h[v] - h[u]);
    if (v == u)
        return v;
    for (int i = LG - 1; i >= 0; i--) {
        int vv = anc[v][i];
        int uu = anc[u][i];
        if (vv != uu && vv && uu) {
            v = vv;
            u = uu;
        }
    }
    return anc[v][0];
}

int cur;

int calc(int v = 1, int p = 1) {
    int s = 0;
    for (int u : adj[v])
        if (u != p) 
            s += calc(u, v);
    s += pos[v];
    cnt[v] = s;
    s += neg[v];
    return s;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int v, u, x, y;
        cin >> v >> u >> x >> y;
        adj[v].pb(u);
        adj[u].pb(v);
        cost[{v, u}] = {x, y};
        cost[{u, v}] = {x, y};
    }
    dfs();
    for (int i = 1; i < n; i++) {
        int v = lca(i, i + 1);
        if (v == i) {
            int u = up(i + 1, h[i + 1] - h[i] - 1);
            pos[i + 1]++;
            neg[u]--;
        }
        else if (v == i + 1) {
            int u = up(i, h[i] - h[i + 1] - 1);
            neg[u]--;
            pos[i]++;
        }
        else {
            int x = up(i, h[i] - h[v] - 1);
            int y = up(i + 1, h[i + 1] - h[v] - 1);
            neg[x]--; neg[y]--;
            pos[i]++; pos[i + 1]++;
        }
    }
    calc();
    
    ll ans = 0;
    for (int i = 2; i <= n; i++) {
        auto [x, y] = cost[{i, anc[i][0]}];
        ans += min(1LL * x * cnt[i], 1LL * y);
    }
    cout << ans;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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