Submission #319331

#	Time	Username	Problem	Language	Result	Execution time	Memory
319331		marlicu	Putovanje (COCI20_putovanje)	C++14	110 / 110	160 ms	26216 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

typedef pair <int, int> pii;

const int MAXN = 2e5 + 5;
const int LOG = 20;

int n, a, b, c1, c2;
vector <pii> veze[MAXN];
vector <pii> cijene;
int lca[LOG][MAXN];
int dubine[MAXN];
int koliko1[MAXN];
int koliko2[MAXN];
int zbroj[MAXN];

void dfs(int cvor, int roditelj, int dubina) {
    dubine[cvor] = dubina;

    for (auto ncvor : veze[cvor]) {
        if (ncvor.X == roditelj) continue;
        dfs(ncvor.X, cvor, dubina + 1);
        lca[0][ncvor.X] = cvor;
    }
}

int nadi_lca(int a, int b) {
    if (dubine[a] < dubine[b]) swap(a, b);

    for (int i = LOG; i >= 0; i--) {
        if (dubine[a] >= dubine[b] + (1 << i)) {
            a = lca[i][a];
        }
    }

    if (a == b) return a;

    for (int i = LOG - 1; i >= 0; i --) {
        if (lca[i][a] != lca[i][b]) {
            a = lca[i][a];
            b = lca[i][b];
        }
    }

    return lca[0][a];
}

void rek(int cvor, int roditelj, int cesta) {
    for (auto ncvor : veze[cvor]) {
        if (ncvor.X == roditelj) continue;
        rek(ncvor.X, cvor, ncvor.Y);
        zbroj[cvor] += zbroj[ncvor.X];
    }

    zbroj[cvor] += koliko1[cvor];

    if (cesta != -1) koliko2[cesta] = zbroj[cvor];
}

void ispis() {
    for (int i = 1; i <= n; i++) {
        cout << i << " : ";
        for (auto nx : veze[i]) cout << nx.X << " ";
        cout << '\n';
    }
    cout << '\n';

    for (int i = 1; i <= n; i++) cout << dubine[i] << " ";
    cout << '\n'; cout << '\n';

    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= n; j++) {
            cout << lca[i][j] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

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

    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b >> c1 >> c2;
        veze[a].push_back({b, i});
        veze[b].push_back({a, i});
        cijene.push_back({c1, c2});
    }

    dfs(1, -1, 0);

    //ispis();

    for (int i = 1; i < LOG; i++) {
        for (int j = 1; j <= n; j++) {
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
        }
    }

    //ispis();

    for (int i = 1; i < n; i++) {
        int zajednicki = nadi_lca(i, i + 1);
        koliko1[i]++;
        koliko1[i + 1]++;
        koliko1[zajednicki] -= 2;
    }

    rek(1, -1, -1);

    long long ukupno = 0;
    for (int i = 0; i < n - 1; i++) {
        ukupno += min((long long)koliko2[i] * cijene[i].X, (long long)cijene[i].Y);
    }
    cout << ukupno << '\n';

    return 0;
}

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