Submission #210030

#	Time	Username	Problem	Language	Result	Execution time	Memory
210030		apostoldaniel854	Putovanje (COCI20_putovanje)	C++14	110 / 110	241 ms	24188 KiB

putovanje

/*
Problem: https://oj.uz/problem/view/COCI20_putovanje
*/


#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 2e5, LG = 20;

struct Edge {
    int x;
    int y;
    int c1;
    int c2;
};

Edge e[1 + N];
int p[LG][1 + N];
int d[1 + N];
vector <pair <int, int>> gr[1 + N];

void dfs (int node, int f) {
    p[0][node] = f;
    d[node] = d[f] + 1;
    for (auto son : gr[node])
        if (f != son.first)
            dfs (son.first, node);
}
int n;

void lift () {
    for (int k = 1; k < LG; k++)
        for (int i = 1; i <= n; i++)
            p[k][i] = p[k - 1][p[k - 1][i]];
}

int lca (int a, int b) {
    int k;
    k = LG - 1;
    while (d[a] > d[b]) {
        if (d[p[k][a]] >= d[b])
            a = p[k][a];
        k--;
    }
    k = LG - 1;
    while (d[a] < d[b]) {
        if (d[p[k][b]] >= d[a])
            b = p[k][b];
        k--;
    }
    k = LG - 1;
    while (k >= 0) {
        if (p[k][a] != p[k][b])
            a = p[k][a], b = p[k][b];
        k--;
    }
    if (a != b)
        a = p[0][a];
    return a;
}
int smen[1 + N];

ll ans;

void go (int node, int f) {
    for (auto son : gr[node]) {
        if (son.first == f) continue;
        go (son.first, node);
        smen[node] += smen[son.first];
    }
    for (auto son : gr[node]) {
        if (son.first == f) {
            int edge_id = son.second;
            ans += min (1ll * e[edge_id].c1 * smen[node], 1ll * e[edge_id].c2);
        }
    }
}


int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> e[i].x >> e[i].y >> e[i].c1 >> e[i].c2;
        gr[e[i].x].pb ({e[i].y, i});
        gr[e[i].y].pb ({e[i].x, i});
    }
    dfs (1, 0);
    lift ();
    for (int i = 1; i < n; i++) {
        int a = i, b = i + 1;
        int c = lca (a, b);
        smen[c] -= 2;
        smen[a]++;
        smen[b]++;
    }
    ans = 0;
    go (1, 0);
    cout << ans << "\n";
    return 0;
}

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