제출 #1319147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319147		aaaaaaaa	Putovanje (COCI20_putovanje)	C++20	110 / 110	106 ms	22792 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 100;

vector<pair<int, int>> adj[mxN];
pair<int, int> edge[mxN];
int edge_idx[mxN], pre[mxN];

struct BinaryLifting{
    vector<int> parent, depth;
    vector<vector<int>> dp;
    int N, mxB;

    void init(int n){
    	N = n, mxB = __lg(N) + 5;
    	parent.resize(N + 1), depth.resize(N + 1);
    	dp.resize(N + 5, vector<int>(mxB, 0));
    }

    void dfs(int u = 1, int par = 0){
        parent[u] = par;
        depth[u] = depth[par] + 1;
        dp[u][0] = par;
        for(int i = 1; i < mxB; ++i) dp[u][i] = dp[dp[u][i - 1]][i - 1];
        for(auto [v, i] : adj[u]){
            if(v ^ par){
                edge_idx[v] = i;
                dfs(v, u);
            }
        }
    }

    void done(int u = 1, int par = 0){
        for(auto it : adj[u]){
            if(it.first ^ par){
                done(it.first, u);
                pre[u] += pre[it.first];
            }
        }
    }

    int kth(int u, int k){
        for(int i = 0; i < mxB; ++i){
            if(k & (1ll << i)) u = dp[u][i];
        }
        return u;
    }

    int lca(int u, int v){
        if(depth[u] < depth[v]) swap(u,v);
        u = kth(u, abs(depth[u] - depth[v]));
        if(u == v) return u;
        for(int i = mxB - 1; i >= 0; --i){
            if(dp[u][i] != dp[v][i]){
                u = dp[u][i];
                v = dp[v][i];
            }
        }
        return dp[u][0];
    }

    int dist(int u, int v){
        return depth[u] + depth[v] -2 * depth[lca(u,v)];
    }

    void update(int u, int v){
        int lc = lca(u, v);
        pre[u] += 1, pre[v] += 1, pre[lc] -= 2;
    }

} helper;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0, u, v, c0, c1; i < n - 1; ++i){
        cin >> u >> v >> c0 >> c1;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        edge[i] = {c0, c1};
    }
    helper.init(n);
    helper.dfs();
    for(int i = 1; i <= n - 1; ++i){
        helper.update(i, i + 1);
    }
    helper.done();
    long long ans = 0;
    for(int i = 2; i <= n; ++i){
        ans += (long long) min((long long) edge[edge_idx[i]].first * pre[i], (long long) edge[edge_idx[i]].second);
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65