oj.uz

Submission #319331

# Submission time Handle Problem Language Result Execution time Memory
319331 2020-11-04T20:27:31 Z marlicu Putovanje (COCI20_putovanje) C++14
110 / 110
 160 ms 26216 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 3 ms 5228 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 4 ms 5356 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 21212 KB Output is correct
2 Correct 138 ms 22552 KB Output is correct
3 Correct 149 ms 24316 KB Output is correct
4 Correct 160 ms 26216 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 125 ms 22596 KB Output is correct
7 Correct 75 ms 18268 KB Output is correct
8 Correct 136 ms 22996 KB Output is correct
9 Correct 72 ms 23632 KB Output is correct
10 Correct 70 ms 23264 KB Output is correct
11 Correct 76 ms 24664 KB Output is correct
12 Correct 78 ms 24924 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 5 ms 5484 KB Output is correct
5 Correct 5 ms 5484 KB Output is correct
6 Correct 3 ms 5228 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 4 ms 5356 KB Output is correct
9 Correct 5 ms 5484 KB Output is correct
10 Correct 134 ms 21212 KB Output is correct
11 Correct 138 ms 22552 KB Output is correct
12 Correct 149 ms 24316 KB Output is correct
13 Correct 160 ms 26216 KB Output is correct
14 Correct 5 ms 5356 KB Output is correct
15 Correct 125 ms 22596 KB Output is correct
16 Correct 75 ms 18268 KB Output is correct
17 Correct 136 ms 22996 KB Output is correct
18 Correct 72 ms 23632 KB Output is correct
19 Correct 70 ms 23264 KB Output is correct
20 Correct 76 ms 24664 KB Output is correct
21 Correct 78 ms 24924 KB Output is correct
22 Correct 132 ms 20696 KB Output is correct
23 Correct 107 ms 18808 KB Output is correct
24 Correct 126 ms 20308 KB Output is correct
25 Correct 4 ms 5356 KB Output is correct
26 Correct 41 ms 11996 KB Output is correct
27 Correct 94 ms 18244 KB Output is correct
28 Correct 61 ms 21460 KB Output is correct
29 Correct 84 ms 25048 KB Output is correct
30 Correct 75 ms 24532 KB Output is correct
31 Correct 4 ms 5484 KB Output is correct