Submission #545533

#	Time	Username	Problem	Language	Result	Execution time	Memory
545533		AlperenT	Putovanje (COCI20_putovanje)	C++17	110 / 110	206 ms	37692 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, K = 20;

long long n, a, b, c1, c2, ans, cnt[N], binlift[N][K], depth[N];

struct Edge{
    long long b, c1, c2;
};

vector<Edge> tree[N];

void dfs(int v, int p){
    binlift[v][0] = p;
    for(int i = 1; i < K; i++) binlift[v][i] = binlift[binlift[v][i - 1]][i - 1];

    depth[v] = depth[p] + 1;

    for(auto e : tree[v]){
        if(e.b != p){
            dfs(e.b, v);
        }
    }
}

int lca(int a, int b){
    if(depth[b] > depth[a]) swap(a, b);

    for(int i = K - 1; i >= 0; i--) if(depth[binlift[a][i]] >= depth[b]) a = binlift[a][i];

    if(a == b) return a;

    for(int i = K - 1; i >= 0; i--){
        if(binlift[a][i] != binlift[b][i]){
            a = binlift[a][i], b = binlift[b][i];
        }
    }

    return binlift[a][0];
}

void dfs2(int v, int p){
    for(auto e : tree[v]){
        if(e.b != p){
            dfs2(e.b, v);

            ans += min(e.c1 * cnt[e.b], e.c2);

            cnt[v] += cnt[e.b];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n - 1; i++){
        cin >> a >> b >> c1 >> c2;

        tree[a].push_back({b, c1, c2});
        tree[b].push_back({a, c1, c2});
    }

    dfs(1, 0);

    cnt[1]--, cnt[2]++;

    for(int i = 2; i <= n - 1; i++){
        int c = lca(i, i + 1);

        cnt[c] -= 2;

        cnt[i]++, cnt[i + 1]++;
    }

    dfs2(1, 0);

    cout << ans;
}

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