oj.uz

답안 #957624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957624 2024-04-04T06:17:05 Z vjudge1 Putovanje (COCI20_putovanje) C++17
25 / 110
 278 ms 49832 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) 0
#endif

#define int ll
#define pb push_back
#define ll long long
#define i2 array<int, 2>
#define SZ(x) (int) (x).size()

const int N = 2e5 + 4, LG = 20;

int n, h[N], pos[N], neg[N], cnt[N], anc[N][LG];
vector<int> adj[N];
map<i2, i2> cost;

void dfs(int v = 1, int p = 1) {
    for (int i = 1; i < LG; i++) {
        int u = anc[v][i - 1];
        u = anc[u][i - 1];
        if (u)
            anc[v][i] = u;
    }
    for (int u : adj[v]) {
        if (u != p) {
            anc[u][0] = v;
            h[u] = h[v] + 1;
            dfs(u, v);
        }
    }
}

int up(int v, int k) {
    for (int i = 0; i < LG; i++) {
        if ((1 << i) & k) 
            v = anc[v][i];
        if (!v)
            break;
    }    
    return v;
}

int lca(int v, int u) {
    if (h[v] < h[u]) 
        swap(v, u);
    v = up(v, h[v] - h[u]);
    if (v == u)
        return v;
    for (int i = LG - 1; i >= 0; i--) {
        int vv = anc[v][i];
        int uu = anc[u][i];
        if (vv != uu && vv && uu) {
            v = vv;
            u = uu;
        }
    }
    return anc[v][0];
}

int cur;

void calc(int v = 1, int p = 1) {
    for (int u : adj[v]) 
        if (u != p)
            calc(u, v);
    cur += pos[v];
    cnt[v] = cur;
    cur += neg[v];
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int v, u, x, y;
        cin >> v >> u >> x >> y;
        adj[v].pb(u);
        adj[u].pb(v);
        cost[{v, u}] = {x, y};
        cost[{u, v}] = {x, y};
    }
    dfs();
    for (int i = 1; i < n; i++) {
        int v = lca(i, i + 1);
        if (v == i) {
            int u = up(i + 1, h[i + 1] - h[i] - 1);
            neg[u]--;
            pos[i + 1]++;
        }
        else if (v == i + 1) {
            int u = up(i, h[i] - h[i + 1] - 1);
            neg[u]--;
            pos[i]++;
        }
        else {
            int x = up(i, h[i] - h[v] - 1);
            int y = up(i + 1, h[i + 1] - h[v] - 1);
            neg[x]--; neg[y]--;
            pos[i]++; pos[i + 1]++;
        }
    }
    calc();
    
    ll ans = 0;
    for (int i = 2; i <= n; i++) {
        auto [x, y] = cost[{i, anc[i][0]}];
        ans += min(1LL * x * cnt[i], 1LL * y);
    }
    cout << ans;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 4 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 44588 KB Output is correct
2 Correct 198 ms 45392 KB Output is correct
3 Correct 224 ms 49736 KB Output is correct
4 Correct 255 ms 49832 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 192 ms 43876 KB Output is correct
7 Correct 113 ms 34052 KB Output is correct
8 Correct 239 ms 44368 KB Output is correct
9 Correct 123 ms 46320 KB Output is correct
10 Correct 122 ms 46676 KB Output is correct
11 Correct 128 ms 48172 KB Output is correct
12 Correct 125 ms 48200 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Incorrect 4 ms 11100 KB Output isn't correct
3 Halted 0 ms 0 KB -