oj.uz

Submission #957622

# Submission time Handle Problem Language Result Execution time Memory
957622 2024-04-04T06:08:12 Z vjudge1 Putovanje (COCI20_putovanje) C++17
25 / 110
 236 ms 49748 KB 
#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;

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

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[u]++;
            neg[i + 1]--;
        }
        else if (v == i + 1) {
            int u = up(i, h[i] - h[i + 1] - 1);
            pos[u]++;
            neg[i]--;
        }
        else {
            int x = up(i, h[i] - h[v] - 1);
            int y = up(i + 1, h[i + 1] - h[v] - 1);
            pos[x]++; pos[y]++;
            neg[i]--; neg[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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Incorrect 3 ms 11096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 44368 KB Output is correct
2 Correct 211 ms 45720 KB Output is correct
3 Correct 221 ms 49576 KB Output is correct
4 Correct 236 ms 49748 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 220 ms 43860 KB Output is correct
7 Correct 105 ms 34132 KB Output is correct
8 Correct 191 ms 44368 KB Output is correct
9 Correct 123 ms 46212 KB Output is correct
10 Correct 115 ms 46164 KB Output is correct
11 Correct 129 ms 47504 KB Output is correct
12 Correct 144 ms 47420 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10840 KB Output is correct
2 Incorrect 3 ms 11096 KB Output isn't correct
3 Halted 0 ms 0 KB -