제출 #1166412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166412		sunflower	Putovanje (COCI20_putovanje)	C++17	110 / 110	72 ms	16964 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl

#define left    __left
#define right   __right
#define prev    __prev
#define fi      first
#define se      second

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int numNode;
int timeHLD = 0;

#define MAX_EDGE 200'200
struct Edge {
    int u, v, uniCost, multiCost;

    void input() {
        cin >> u >> v >> uniCost >> multiCost;
    }
} edges[MAX_EDGE + 2];

#define MAX_NODE 200'200
vector <int> adj[MAX_NODE + 2];
int par[MAX_NODE + 2], sz[MAX_NODE + 2], high[MAX_NODE + 2];
int head[MAX_NODE + 2], pos[MAX_NODE + 2];

void dfs(int u) {
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == par[u]) continue;
        par[v] = u;
        high[v] = high[u] + 1;
        dfs(v);
        sz[u] += sz[v];
    }
}

void hld(int u, int root) {
    head[u] = root;
    pos[u] = ++timeHLD;

//    if (u == 4) {
//            debug("herh");
//    debug(pos[u]);
//        exit(0);
//    }

    int nxt = 0;
    for (int v : adj[u]) {
        if (v == par[u]) continue;
        if (nxt == 0 || sz[v] > sz[nxt]) nxt = v;
    }

    if (!nxt) return;
    hld(nxt, root);

    for (int v : adj[u]) {
        if (v == par[u] || v == nxt) continue;
        hld(v, v);
    }
}

struct FenwickTree {
    int bit[MAX_NODE + 2];

    void update(int x, int v) {
        for (; x <= numNode; x += x & (-x))
            bit[x] += v;
    }

    void updateRange(int l, int r, int v) {
        update(l, v);
        update(r + 1, -v);
    }

    int get(int x) {
        int ans = 0;
        for (; x > 0; x -= x & (-x)) ans += bit[x];
        return ans;
    }

    int cal(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
} fen;

void updatePath(int u, int v) {
    while (head[u] != head[v]) {
        if (high[head[u]] < high[head[v]]) swap(u, v);
        fen.updateRange(pos[head[u]], pos[u], 1);

        u = par[head[u]];
    }

    if (pos[u] > pos[v]) swap(u, v);
    if (pos[u] + 1 <= pos[v]) fen.updateRange(pos[u] + 1, pos[v], 1);
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> numNode;
    FOR(i, 1, numNode - 1) {
        edges[i].input();
        int u = edges[i].u, v = edges[i].v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    timeHLD = 0;
    dfs(1);
    hld(1, 1);

    FOR(u, 1, numNode - 1) updatePath(u, u + 1);

    ll ans = 0;
    FOR(i, 1, numNode - 1) {
        int u = edges[i].u, v = edges[i].v, uni = edges[i].uniCost, multi = edges[i].multiCost;

        if (u != par[v]) swap(u, v);
        // now v is child of u;
        ans += min(1LL * multi, 1LL * uni * fen.get(pos[v]));
    }

    cout << ans;

    return 0;
}

/* Discipline - Calm */

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