oj.uz

Submission #957621

# Submission time Handle Problem Language Result Execution time Memory
957621 2024-04-04T06:04:32 Z ArashJafariyan Putovanje (COCI20_putovanje) C++17
25 / 110
 205 ms 38060 KB 
#include <bits/stdc++.h>
using namespace std;

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

#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 = 0) {
    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;
    // cout << "\n--------------------\n" << anc[2][0];
}

int 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 4 ms 8796 KB Output is correct
2 Incorrect 3 ms 9048 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 164 ms 33104 KB Output is correct
2 Correct 173 ms 34516 KB Output is correct
3 Correct 184 ms 36020 KB Output is correct
4 Correct 205 ms 38060 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 152 ms 32624 KB Output is correct
7 Correct 100 ms 25784 KB Output is correct
8 Correct 165 ms 33004 KB Output is correct
9 Correct 111 ms 33876 KB Output is correct
10 Correct 101 ms 32852 KB Output is correct
11 Correct 112 ms 36664 KB Output is correct
12 Correct 116 ms 36432 KB Output is correct

Subtask #3
0 / 65.0

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