Submission #1150656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150656		jmuzhen	Putovanje (COCI20_putovanje)	C++20	110 / 110	81 ms	19784 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
 
struct Edge {
    int u, v;
    int c1, c2;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    cin >> N;
    vector<Edge> edges(N-1);
    vector<vector<pair<int,int>>> adj(N+1); // adj[node] = vector of (neighbor, edge index)
 
    for(int i=0; i < N-1; i++){
        int A, B, C1, C2;
        cin >> A >> B >> C1 >> C2;
        edges[i] = {A, B, C1, C2};
        adj[A].push_back({B, i});
        adj[B].push_back({A, i});
    }
 
    // Root the tree at node 1. We'll use BFS to compute parent and depth.
    vector<int> par(N+1, 0), depth(N+1, 0), parentEdge(N+1, -1);
    vector<bool> visited(N+1, false);
    queue<int> q;
    visited[1] = true;
    par[1] = 0;
    depth[1] = 0;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto &pr : adj[u]){
            int v = pr.first, eidx = pr.second;
            if(!visited[v]){
                visited[v] = true;
                par[v] = u;
                depth[v] = depth[u] + 1;
                parentEdge[v] = eidx;
                q.push(v);
            }
        }
    }
 
    // Build binary lifting table for LCA.
    int LOG = 0;
    while((1 << LOG) <= N) LOG++;
    vector<vector<int>> up(N+1, vector<int>(LOG,0));
    for (int i=1; i<=N; i++){
        up[i][0] = par[i];
    }
    for (int j=1; j<LOG; j++){
        for (int i=1; i<=N; i++){
            int mid = up[i][j-1];
            up[i][j] = (mid == 0 ? 0 : up[mid][j-1]);
        }
    }
 
    auto lca = [&](int u, int v) -> int {
        if(depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int j = 0; diff; j++){
            if(diff & 1)
                u = up[u][j];
            diff >>= 1;
        }
        if(u == v)
            return u;
        for (int j = LOG-1; j >= 0; j--){
            if(up[u][j] != up[v][j]){
                u = up[u][j];
                v = up[v][j];
            }
        }
        return par[u];
    };
 
    // Frequency array: for each journey from town i to i+1, add +1 at endpoints and -2 at LCA.
    vector<long long> freq(N+1, 0);
    for(int i = 1; i < N; i++){
        int u = i, v = i+1;
        int w = lca(u, v);
        freq[u]++;
        freq[v]++;
        freq[w] -= 2;
    }
 
    // Process nodes in order of descending depth (so that every child is processed before its parent)
    vector<int> order(N);
    for (int i = 0; i < N; i++){
        order[i] = i+1;
    }
    sort(order.begin(), order.end(), [&](int a, int b){
        return depth[a] > depth[b];
    });
 
    long long ans = 0;
    for(auto node : order){
        if(node == 1) continue; // Skip the root (no parent edge)
        int e = parentEdge[node];
        long long useCount = freq[node];
        long long costSingle = useCount * 1LL * edges[e].c1;
        long long costMulti  = edges[e].c2;
        ans += min(costSingle, costMulti);
        freq[par[node]] += freq[node]; // Propagate the frequency upward.
    }
 
    cout << ans << "\n";
    return 0;
}

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