oj.uz

Submission #857802

# Submission time Handle Problem Language Result Execution time Memory
857802 2023-10-07T02:19:21 Z trieghv Putovanje (COCI20_putovanje) C++14
110 / 110
 125 ms 64856 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]) {
            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) {
    dp[u] += t[u];
    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];
    }
    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);

    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 31064 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31152 KB Output is correct
4 Correct 7 ms 31388 KB Output is correct
5 Correct 7 ms 31280 KB Output is correct
6 Correct 7 ms 31068 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 60252 KB Output is correct
2 Correct 88 ms 61520 KB Output is correct
3 Correct 109 ms 64856 KB Output is correct
4 Correct 115 ms 64080 KB Output is correct
5 Correct 6 ms 31320 KB Output is correct
6 Correct 87 ms 59968 KB Output is correct
7 Correct 60 ms 51796 KB Output is correct
8 Correct 125 ms 60140 KB Output is correct
9 Correct 61 ms 60756 KB Output is correct
10 Correct 56 ms 60392 KB Output is correct
11 Correct 60 ms 63316 KB Output is correct
12 Correct 68 ms 63176 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31152 KB Output is correct
4 Correct 7 ms 31388 KB Output is correct
5 Correct 7 ms 31280 KB Output is correct
6 Correct 7 ms 31068 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31204 KB Output is correct
10 Correct 103 ms 60252 KB Output is correct
11 Correct 88 ms 61520 KB Output is correct
12 Correct 109 ms 64856 KB Output is correct
13 Correct 115 ms 64080 KB Output is correct
14 Correct 6 ms 31320 KB Output is correct
15 Correct 87 ms 59968 KB Output is correct
16 Correct 60 ms 51796 KB Output is correct
17 Correct 125 ms 60140 KB Output is correct
18 Correct 61 ms 60756 KB Output is correct
19 Correct 56 ms 60392 KB Output is correct
20 Correct 60 ms 63316 KB Output is correct
21 Correct 68 ms 63176 KB Output is correct
22 Correct 78 ms 58704 KB Output is correct
23 Correct 71 ms 56040 KB Output is correct
24 Correct 75 ms 56656 KB Output is correct
25 Correct 9 ms 31324 KB Output is correct
26 Correct 31 ms 43396 KB Output is correct
27 Correct 64 ms 53740 KB Output is correct
28 Correct 54 ms 59852 KB Output is correct
29 Correct 74 ms 63184 KB Output is correct
30 Correct 60 ms 63300 KB Output is correct
31 Correct 6 ms 31324 KB Output is correct