제출 #1255915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255915		Dreamy_lovesper	Putovanje (COCI20_putovanje)	C++20	110 / 110	138 ms	32004 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define pb push_back
#define mpp make_pair
#define sz(s) (int)s.size()
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (ll i = a; i <= b; i++)
#define fd(i, b, a) for (ll i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)
#define LoveTime chrono::steady_clock::now().time_since_epoch().count()

const ll Mod = 998244353;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 200'007
ll n, sad, pref[mxn];
ll h[mxn], f[21][mxn];

struct Edge {
    ll v, w1, w2;
};
vector<Edge> graph[mxn];

void dfsLca(ll u) {
    for(auto&[v, w1, w2]: graph[u]) {
        if(v == f[0][u]) continue;
        f[0][v] = u; h[v] = h[u] + 1;
        fu(j, 1, 19) f[j][v] = f[j - 1][f[j - 1][v]];
        dfsLca(v);
    }
}

ll lca(ll u, ll v) {
    if(h[u] < h[v]) swap(u, v);
    ll k = h[u] - h[v];
    fu(j, 0, 19) if(Bitc(k, j)) u = f[j][u];
    if(u == v) return u;
    fd(j, 19, 0) if(f[j][u] != f[j][v]) u = f[j][u], v = f[j][v];
    return f[0][u];
}

void dfsCalc(ll u, ll p) {
    for(auto&[v, w1, w2]: graph[u]) {
        if(v == p) continue;
        dfsCalc(v, u);
        pref[u] += pref[v];
        sad += min(pref[v] * w1, w2);
    }
}

void lovesper(const ll &TestCase) {
    cin >> n;
    fu(i, 2, n) {
        ll u, v, w1, w2; cin >> u >> v >> w1 >> w2;
        graph[u].pb({v, w1, w2});
        graph[v].pb({u, w1, w2});
    }

    dfsLca(1);
    fu(i, 1, n - 1) {
        ll p = lca(i, i + 1);
        pref[i]++; pref[i + 1]++;
        pref[p] -= 2;
    }
    
    dfsCalc(1, 0);
    cout << sad;
    
}

signed main() {
    LIFESUCK

    #define name "loveser"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);

    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

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