oj.uz

Submission #857800

# Submission time Handle Problem Language Result Execution time Memory
857800 2023-10-07T02:14:15 Z trieghv Putovanje (COCI20_putovanje) C++14
110 / 110
 104 ms 63452 KB 
/* Author : Do Thanh Triet - Tran Hung Dao High School for Gifted Student */
/*      Algorithms + Data structures + Arts programming = Program <3      */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ft first
#define sc second
#define oset tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for (int i = (r); i >= (l); --i)
#define all(x) x.begin(), x.end()

#define ON_BIT(mask, i) ((mask) | (1LL << i))
#define OFF_BIT(mask, i) ((mask) & ~(1LL << i))
#define C_BIT(mask) __builtin_popcountll(mask)
#define BIT(mask, i) ((mask) & (1LL << i))
#define F1BIT(mask) __builtin_ffsll(mask)
#define endl '\n'
#define int ll

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 9;
const int N =  2e5 + 9;
const int MOD = 1e9 + 7;
const long long INF = 0x3f;
const long long oo = 1e18 +  9;

#define TASK "code"

int n;
ii cost[maxn];
vector<ii>adj[maxn];

int h[maxn], p[maxn][21];
int t[maxn], dp[maxn];

int cnt[maxn];

void predfs(int u, int par) {
    for (ii &x : adj[u]) {
        int v = x.ft;
        if (v == par) continue;
        h[v] = h[u] + 1;
        p[v][0] = u;
        for (int j = 1; (1<<j) <= n; ++j) p[v][j] = p[p[v][j - 1]][j - 1];
        predfs(v, u);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int log = log2(h[u]);
    FORD(i, log, 0) {
        if (h[u] - (1<<i) >= h[v]) {
            u = p[u][i];
        }
    }
    if (u == v) return u;
    FORD(i, log, 0) {
        if (p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

void dfs_cal(int u, int par, int pos) {
    for (ii &x : adj[u]) {
        int v = x.ft, id = x.sc;
        if (v == par) continue;
        dfs_cal(v, u, id);
        dp[u] += dp[v];
    }
    dp[u] += t[u];
    if (pos != -1) cnt[pos] = dp[u];
}

void solve() {
    cin >> n;
    FOR(i, 1, n - 1) {
        int u, v, id;
        id = i;
        cin >> u >> v >> cost[id].ft >> cost[id].sc;
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
    }
    predfs(1, 0);
    FOR(i,1,n - 1) {
        t[i]++;
        t[i + 1]++;
        t[lca(i, i + 1)] -=2;
    }

    dfs_cal(1, 0, -1);

    int res = 0;
    FOR(i, 1, n - 1) {
        res += min(cost[i].ft * cnt[i], cost[i].sc);
    }
    cout<<res;
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen(TASK ".inp", "r", stdin);
    //freopen(TASK ".out", "w", stdout);
    solve();
    return 0;
}
//Take a deep breath, don't be nervous, read the question slowly and understand the question, the question is often simpler than you think.
/*
Input:

*/
/*
Output:

*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 7 ms 29304 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 58448 KB Output is correct
2 Correct 90 ms 59984 KB Output is correct
3 Correct 103 ms 63452 KB Output is correct
4 Correct 104 ms 62452 KB Output is correct
5 Correct 6 ms 29272 KB Output is correct
6 Correct 87 ms 58588 KB Output is correct
7 Correct 55 ms 50272 KB Output is correct
8 Correct 100 ms 58624 KB Output is correct
9 Correct 59 ms 58960 KB Output is correct
10 Correct 56 ms 58556 KB Output is correct
11 Correct 61 ms 61776 KB Output is correct
12 Correct 65 ms 61440 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 7 ms 29304 KB Output is correct
3 Correct 6 ms 29276 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 8 ms 29276 KB Output is correct
10 Correct 93 ms 58448 KB Output is correct
11 Correct 90 ms 59984 KB Output is correct
12 Correct 103 ms 63452 KB Output is correct
13 Correct 104 ms 62452 KB Output is correct
14 Correct 6 ms 29272 KB Output is correct
15 Correct 87 ms 58588 KB Output is correct
16 Correct 55 ms 50272 KB Output is correct
17 Correct 100 ms 58624 KB Output is correct
18 Correct 59 ms 58960 KB Output is correct
19 Correct 56 ms 58556 KB Output is correct
20 Correct 61 ms 61776 KB Output is correct
21 Correct 65 ms 61440 KB Output is correct
22 Correct 86 ms 56916 KB Output is correct
23 Correct 67 ms 52560 KB Output is correct
24 Correct 77 ms 53336 KB Output is correct
25 Correct 6 ms 29276 KB Output is correct
26 Correct 31 ms 41860 KB Output is correct
27 Correct 67 ms 50260 KB Output is correct
28 Correct 58 ms 57960 KB Output is correct
29 Correct 61 ms 61524 KB Output is correct
30 Correct 60 ms 61340 KB Output is correct
31 Correct 6 ms 29272 KB Output is correct