oj.uz

Submission #854409

# Submission time Handle Problem Language Result Execution time Memory
854409 2023-09-27T11:04:28 Z wakandaaa Putovanje (COCI20_putovanje) C++17
110 / 110
 110 ms 32860 KB 
#include <bits/stdc++.h>

using namespace std;

#define file "COCI20_putovanje"

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 2e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n;
vector<pair<int, int> > adj[N];
int h[N], par[N][lg + 1];
int d[N];
int single[N], multi[N];
int cnt[N];

void dfs(int u, int p) {
    par[u][0] = p;
    for (int i = 1; i < 20; ++i) par[u][i] = par[par[u][i - 1]][i - 1];
    for (auto [v, id] : adj[u]) if (v != p) {
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    for (int i = 19; i >= 0; --i) if (h[par[u][i]] >= h[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i) if (par[u][i] != par[v][i]) {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

void rdfs(int u, int p, int id) {
    for (auto [v, id] : adj[u]) if (v != p) {
        rdfs(v, u, id);
        d[u] += d[v];
    }
    cnt[id] = d[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v >> single[i] >> multi[i];
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    h[0] = -1;
    dfs(1, 0);

    for (int i = 1; i < n; ++i) {
        d[i]++;
        d[i + 1]++;
        d[lca(i, i + 1)] -= 2;
    }
    rdfs(1, 0, 0);
    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        res += min(1LL * cnt[i] * single[i], 1LL * multi[i]);
    }

    cout << res;

    return 0;
}

/*
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3

11
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 3 ms 11096 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 27984 KB Output is correct
2 Correct 89 ms 29228 KB Output is correct
3 Correct 101 ms 32860 KB Output is correct
4 Correct 110 ms 31960 KB Output is correct
5 Correct 2 ms 10840 KB Output is correct
6 Correct 90 ms 27792 KB Output is correct
7 Correct 49 ms 23644 KB Output is correct
8 Correct 82 ms 27680 KB Output is correct
9 Correct 66 ms 30032 KB Output is correct
10 Correct 62 ms 29700 KB Output is correct
11 Correct 67 ms 30544 KB Output is correct
12 Correct 67 ms 30588 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11096 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10584 KB Output is correct
8 Correct 3 ms 11096 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 85 ms 27984 KB Output is correct
11 Correct 89 ms 29228 KB Output is correct
12 Correct 101 ms 32860 KB Output is correct
13 Correct 110 ms 31960 KB Output is correct
14 Correct 2 ms 10840 KB Output is correct
15 Correct 90 ms 27792 KB Output is correct
16 Correct 49 ms 23644 KB Output is correct
17 Correct 82 ms 27680 KB Output is correct
18 Correct 66 ms 30032 KB Output is correct
19 Correct 62 ms 29700 KB Output is correct
20 Correct 67 ms 30544 KB Output is correct
21 Correct 67 ms 30588 KB Output is correct
22 Correct 77 ms 26724 KB Output is correct
23 Correct 62 ms 23892 KB Output is correct
24 Correct 71 ms 26704 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 30 ms 17340 KB Output is correct
27 Correct 59 ms 23968 KB Output is correct
28 Correct 58 ms 26708 KB Output is correct
29 Correct 68 ms 30564 KB Output is correct
30 Correct 65 ms 30232 KB Output is correct
31 Correct 2 ms 10840 KB Output is correct