제출 #223188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
223188		lyc	Putovanje (COCI20_putovanje)	C++14	110 / 110	147 ms	17784 KiB

putovanje

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

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 2e5+5;

int N;
vector<tuple<int,int,int>> al[MX_N];

struct FenwickTree {
    vector<int> ft;
    int n;
    void init(int _n) {
        n = _n;
        ft.assign(n+1,0);
    }
    void u(int i, int x) { for (; i <= n; i += i&-i) ft[i] += x; }
    int query(int i) { int sum = 0; for (; i; i -= i&-i) sum += ft[i]; return sum; }
    void update(int i, int j, int x) { u(i,x); u(j+1,-x); }
} ft;

pair<int,int> weight[MX_N];
/* custom ds of you choice */
int cnt = 1;
int pa[MX_N], dep[MX_N];
int heavy[MX_N], head[MX_N], pos[MX_N];
// heavy stores the heavy child of this vertex
// head stores the head/top of the chain this vertex is in
// pos relabels vertices to work with custom ds of your choice

int dfs(int u, int p, int d) {
    pa[u] = p;
    dep[u] = d;
    heavy[u] = -1;
    int sz = 1, mchild = 0;
    for (auto e : al[u]) {
        int v = get<0>(e);
        if (v == p) continue;
        weight[v] = make_pair(get<1>(e),get<2>(e));
        int cs = dfs(v, u, d+1);
        sz += cs;
        if (cs > mchild) {
            mchild = cs;
            heavy[u] = v;
        }
    }
    return sz;
}

void hld(int u, int p, int h) {
    head[u] = h;
    pos[u] = cnt++;
    if (heavy[u] != -1) hld(heavy[u], u, h);
    for (auto e : al[u]) {
        int v = get<0>(e);
        if (v == p) continue;
        if (v != p and v != heavy[u]) {
            hld(v, u, v);
        }
    }
}

void update_path(int a, int b, int v) {
    for (; head[a] != head[b]; a = pa[head[a]]) {   // go up the chains
        if (dep[head[a]] < dep[head[b]]) swap(a, b);
        ft.update(pos[head[a]], pos[a], v);   // update the entire chain
    }
    if (a == b) return;
    if (dep[a] < dep[b]) swap(a, b);
    ft.update(pos[b]+1, pos[a], v);   // update part of the chain required
}

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

    cin >> N;
    FOR(i,1,N-1){
        int A, B, C, D; cin >> A >> B >> C >> D;
        al[A].emplace_back(B,C,D);
        al[B].emplace_back(A,C,D);
    }

    dfs(1,0,0);
    hld(1,0,1);
    ft.init(N);
    FOR(i,1,N-1){
        update_path(i,i+1,1);
    }

    long long ans = 0;
    FOR(i,2,N){
        //cout << i << " :: " << ft.query(pos[i]) << endl;
        ans += min(1LL * weight[i].first * ft.query(pos[i]), (long long)weight[i].second);
    }
    cout << ans << '\n';
}

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