Submission #968681

#	Time	Username	Problem	Language	Result	Execution time	Memory
968681		RandomUser	Putovanje (COCI20_putovanje)	C++17	110 / 110	185 ms	27356 KiB

putovanje

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65