Submission #530520

#	Time	Username	Problem	Language	Result	Execution time	Memory
530520		Servus2022	Putovanje (COCI20_putovanje)	C++14	110 / 110	119 ms	26332 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
constexpr int NMAX = 2e5 + 5;

struct Edge {
    int X, Y;
    int Cost_1, Cost_2;
};

int N;
vector <int> G[NMAX];
Edge E[NMAX];

int fr[NMAX];

int Level[NMAX];
int Dad[18][NMAX];

int Add[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i < N; ++ i ) {
        cin >> E[i].X >> E[i].Y >> E[i].Cost_1 >> E[i].Cost_2;
        G[E[i].X].push_back(i);
        G[E[i].Y].push_back(i);
    }
}

void Dfs (int Node, int dad = 0) {
    Dad[0][Node] = dad;
    Level[Node] = Level[dad] + 1;

    for (int i = 1; i < 18; ++ i )
        Dad[i][Node] = Dad[i-1][Dad[i-1][Node]];

    for (auto it : G[Node]) {
        int to = (E[it].X == Node ? E[it].Y : E[it].X);

        if (to == dad) continue;

        Dfs(to, Node);
    }
}

int Parent (int Node, int who) {
    for (int i = 0; i < 18; ++ i )
        if ((who&(1<<i))) Node = Dad[i][Node];

    return Node;
}

int LCA (int x, int y) {
    if (Level[x] > Level[y]) swap(x, y);

    y = Parent(y, Level[y] - Level[x]);

    if (x == y) return x;

    for (int i = 17; i >= 0; -- i ) {
        if (Dad[i][x] != Dad[i][y]) {
            x = Dad[i][x];
            y = Dad[i][y];
        }
    }

    return Dad[0][x];
}

void Precalculare () {
    Dfs(1);

    for (int i = 1; i < N; ++ i ) {
        int z = LCA(i, i+1);

        Add[i]++;
        Add[i+1]++;
        Add[z] -= 2;
    }
}

void Collect (int Node, int dad = -1, int ind = 0) {
    for (auto it : G[Node]) {
        int to = (E[it].X == Node ? E[it].Y : E[it].X);

        if (to == dad) continue;

        Collect(to, Node, it);
        Add[Node] += Add[to];
    }

    fr[ind] = Add[Node];
}

void Solve () {
    Collect(1);

    LL ans = 0;

    for (int i = 1; i < N; ++ i )
        ans += min(1LL * E[i].Cost_2, 1LL * fr[i] * E[i].Cost_1);

    cout << ans << '\n';
}

int main()
{
    Read();
    Precalculare();
    Solve();

    return 0;
}

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