oj.uz

Submission #857797

# Submission time Handle Problem Language Result Execution time Memory
857797 2023-10-07T02:09:25 Z trieghv Putovanje (COCI20_putovanje) C++14
0 / 110
 104 ms 63288 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 "Putovanje"

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]) {
            v = 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Incorrect 6 ms 29276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 58312 KB Output is correct
2 Correct 85 ms 59848 KB Output is correct
3 Correct 97 ms 63288 KB Output is correct
4 Correct 97 ms 62664 KB Output is correct
5 Correct 6 ms 29276 KB Output is correct
6 Correct 104 ms 58448 KB Output is correct
7 Incorrect 53 ms 50336 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Incorrect 6 ms 29276 KB Output isn't correct
3 Halted 0 ms 0 KB -