oj.uz

Submission #957617

# Submission time Handle Problem Language Result Execution time Memory
957617 2024-04-04T05:51:40 Z vjudge1 Putovanje (COCI20_putovanje) C++17
25 / 110
 193 ms 38280 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;
        else 
            break;
    }
    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);
        debug(i, v);
        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;
}

Compilation message

putovanje.cpp: In function 'void solve()':
putovanje.cpp:7:20: warning: statement has no effect [-Wunused-value]
    7 | #define debug(...) 0
      |                    ^
putovanje.cpp:90:9: note: in expansion of macro 'debug'
   90 |         debug(i, v);
      |         ^~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 3 ms 9052 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 151 ms 33120 KB Output is correct
2 Correct 154 ms 34256 KB Output is correct
3 Correct 193 ms 36256 KB Output is correct
4 Correct 189 ms 38280 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 151 ms 32596 KB Output is correct
7 Correct 110 ms 25976 KB Output is correct
8 Correct 151 ms 33108 KB Output is correct
9 Correct 103 ms 33548 KB Output is correct
10 Correct 98 ms 32924 KB Output is correct
11 Correct 107 ms 36588 KB Output is correct
12 Correct 109 ms 36544 KB Output is correct

Subtask #3
0 / 65.0

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