Submission #464474

#	Time	Username	Problem	Language	Result	Execution time	Memory
464474		TheScrasse	Putovanje (COCI20_putovanje)	C++17	110 / 110	143 ms	30544 KiB

putovanje

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 200010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll w1, w2, wu[maxn][2], pr[maxn], dp[maxn];
bool vis[maxn];
vector<array<ll, 3>> adj[maxn];
vector<ll> qdg[maxn];

ll find(ll x) {
    if (pr[x] == x) return x;
    return pr[x] = find(pr[x]);
}

void onion(ll a, ll b) { // (a, b) = (high, low)
    a = find(a); b = find(b);
    if (a == b) return;
    pr[b] = a;
}

void init(ll s) {
    ll i;
    for (i = 1; i <= n; i++) vis[i] = false;
}

void dfs(ll s) {
    ll l;
    vis[s] = true;

    for (auto u : qdg[s]) {
        if (!vis[u]) continue;
        l = find(u);
        dp[s]++; dp[u]++; dp[l] -= 2;
    }

    for (auto [u, w1, w2] : adj[s]) {
        if (vis[u]) {
            wu[s][0] = w1; wu[s][1] = w2; continue;
        }
        dfs(u);
        onion(s, u);
    }
}

void calc(ll s) {
    vis[s] = true;
    for (auto [u, w1, w2] : adj[s]) {
        if (vis[u]) continue;
        calc(u);
        dp[s] += dp[u];
    }
    if (dp[s] == 0) return;
    res += min(dp[s] * wu[s][0], wu[s][1]);
}

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n;
    for (i = 1; i <= n - 1; i++) {
        cin >> a >> b >> w1 >> w2;
        adj[a].pb({b, w1, w2}); adj[b].pb({a, w1, w2});
    }

    for (i = 1; i <= n; i++) {
        if (i != 1) qdg[i].pb(i - 1);
        if (i != n) qdg[i].pb(i + 1);
    }

    for (i = 1; i <= n; i++) pr[i] = i;

    dfs(1);
    init(1);
    calc(1);

    /* for (i = 1; i <= n; i++) cout << dp[i] << ' ';
    cout << nl; */

    cout << res << nl;

    return 0;
}

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