oj.uz

Submission #968681

# Submission time Handle Problem Language Result Execution time Memory
968681 2024-04-23T20:08:01 Z RandomUser Putovanje (COCI20_putovanje) C++17
110 / 110
 185 ms 27356 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int LOG = 20;
const int maxn = 2e5 + 5;
 
ll ans = 0;
vector<array<int, 3> > graph[maxn];
int up[maxn][LOG], depth[maxn], diff[maxn], dp[maxn];
 
void dfs1(int u, int p) {
    for(int i=1; i<LOG; i++) up[u][i] = up[up[u][i-1]][i-1];
 
    for(auto &[v, c1, c2] : graph[u]) {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        dfs1(v, u);
    }
}
 
int jmp(int x, int d) {
    for(int j=LOG-1; j>=0; j--)
        if(d & (1 << j)) x = up[x][j];
    return x;
}
 
int get_lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
 
    a = jmp(a, depth[a] - depth[b]);
    if(a == b) return a;
    for(int j=LOG-1; j>=0; j--)
        if(up[a][j] != up[b][j])
            a = up[a][j], b = up[b][j];
 
    return up[a][0];
}
 
void dfs2(int u, int p, int a, int b) {
    dp[u] = diff[u];
 
    for(auto &[v, c1, c2] : graph[u]) {
        if(v == p) continue;
        dfs2(v, u, c1, c2);
        dp[u] += dp[v];
    }
 
    ans += min(1ll * dp[u] * a, 1ll * b);
}
 
int32_t main() {
    int n;
    cin >> n;
 
    for(int i=0; i<n-1; i++) {
        int a, b, c1, c2;
        cin >> a >> b >> c1 >> c2;
        graph[a].push_back({ b, c1, c2 });
        graph[b].push_back({ a, c1, c2 });
    }
 
    dfs1(1, 0);
 
    for(int i=1; i<n; i++) {
        diff[i]++; 
        diff[i+1]++;
        diff[get_lca(i, i+1)] -= 2;
    }
 
    dfs2(1, 0, 0, 0);
 
    cout << ans << '\n';
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24472 KB Output is correct
2 Correct 120 ms 25684 KB Output is correct
3 Correct 179 ms 27356 KB Output is correct
4 Correct 185 ms 26444 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 117 ms 24148 KB Output is correct
7 Correct 78 ms 19840 KB Output is correct
8 Correct 148 ms 24236 KB Output is correct
9 Correct 126 ms 24456 KB Output is correct
10 Correct 108 ms 24104 KB Output is correct
11 Correct 145 ms 25172 KB Output is correct
12 Correct 128 ms 25172 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6748 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 5 ms 6748 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 120 ms 24472 KB Output is correct
11 Correct 120 ms 25684 KB Output is correct
12 Correct 179 ms 27356 KB Output is correct
13 Correct 185 ms 26444 KB Output is correct
14 Correct 3 ms 6492 KB Output is correct
15 Correct 117 ms 24148 KB Output is correct
16 Correct 78 ms 19840 KB Output is correct
17 Correct 148 ms 24236 KB Output is correct
18 Correct 126 ms 24456 KB Output is correct
19 Correct 108 ms 24104 KB Output is correct
20 Correct 145 ms 25172 KB Output is correct
21 Correct 128 ms 25172 KB Output is correct
22 Correct 154 ms 21840 KB Output is correct
23 Correct 112 ms 20816 KB Output is correct
24 Correct 114 ms 21688 KB Output is correct
25 Correct 3 ms 6492 KB Output is correct
26 Correct 52 ms 13604 KB Output is correct
27 Correct 121 ms 20820 KB Output is correct
28 Correct 90 ms 23100 KB Output is correct
29 Correct 124 ms 25324 KB Output is correct
30 Correct 121 ms 24836 KB Output is correct
31 Correct 3 ms 6560 KB Output is correct