oj.uz

Submission #957627

# Submission time Handle Problem Language Result Execution time Memory
957627 2024-04-04T06:24:20 Z vjudge1 Putovanje (COCI20_putovanje) C++17
110 / 110
 251 ms 49884 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;

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 5 ms 11104 KB Output is correct
4 Correct 5 ms 11100 KB Output is correct
5 Correct 4 ms 11100 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10856 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 44484 KB Output is correct
2 Correct 199 ms 45468 KB Output is correct
3 Correct 230 ms 49884 KB Output is correct
4 Correct 247 ms 49748 KB Output is correct
5 Correct 2 ms 10844 KB Output is correct
6 Correct 193 ms 43956 KB Output is correct
7 Correct 112 ms 33992 KB Output is correct
8 Correct 201 ms 44328 KB Output is correct
9 Correct 128 ms 46424 KB Output is correct
10 Correct 119 ms 46676 KB Output is correct
11 Correct 161 ms 48252 KB Output is correct
12 Correct 123 ms 48344 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 4 ms 11100 KB Output is correct
3 Correct 5 ms 11104 KB Output is correct
4 Correct 5 ms 11100 KB Output is correct
5 Correct 4 ms 11100 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 2 ms 10856 KB Output is correct
8 Correct 3 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 245 ms 44484 KB Output is correct
11 Correct 199 ms 45468 KB Output is correct
12 Correct 230 ms 49884 KB Output is correct
13 Correct 247 ms 49748 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 193 ms 43956 KB Output is correct
16 Correct 112 ms 33992 KB Output is correct
17 Correct 201 ms 44328 KB Output is correct
18 Correct 128 ms 46424 KB Output is correct
19 Correct 119 ms 46676 KB Output is correct
20 Correct 161 ms 48252 KB Output is correct
21 Correct 123 ms 48344 KB Output is correct
22 Correct 245 ms 45264 KB Output is correct
23 Correct 223 ms 40760 KB Output is correct
24 Correct 251 ms 45136 KB Output is correct
25 Correct 3 ms 11100 KB Output is correct
26 Correct 84 ms 26316 KB Output is correct
27 Correct 194 ms 40020 KB Output is correct
28 Correct 103 ms 43080 KB Output is correct
29 Correct 159 ms 48356 KB Output is correct
30 Correct 131 ms 48836 KB Output is correct
31 Correct 3 ms 11100 KB Output is correct