oj.uz

Submission #857822

# Submission time Handle Problem Language Result Execution time Memory
857822 2023-10-07T03:53:58 Z hct_2so1 Putovanje (COCI20_putovanje) C++17
110 / 110
 93 ms 28500 KB 
#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((ll) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))

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

using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int M = 6e5;
const int mod = 998244353;
const int INF = 1e9 + 7;
const ll oo = 2e18;
const double eps = 1e-1;
const long double pi = 2*acos(0.0);

struct edge
{
    int u, v, c1, c2;
    edge(int _u = 0, int _v = 0, int _c1 = 0, int _c2 = 0)
    {
        u = _u, v = _v, c1 = _c1, c2 = _c2;
    }
    int other(int x)
    {
        return x ^ u ^ v;
    }
} e[N];

int n, d[N], pa[N][18];
vector<int> ar[N];

void Input(void)
{
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        int u, v, c1, c2;
        cin >> u >> v >> c1 >> c2;
        e[i] = edge(u, v, c1, c2);
        ar[u].push_back(i);
        ar[v].push_back(i);
    }
}

void dfs(int u)
{
    for (int id : ar[u])
    {
        int v = e[id].other(u);
        if (v != pa[u][0])
        {
            pa[v][0] = u, d[v] = d[u] + 1;
            for (int i = 1; i <= 17; i ++) pa[v][i] = pa[pa[v][i - 1]][i - 1];
            dfs(v);
        }
    }
}

int lca(int u, int v)
{
    if (d[u] < d[v]) return lca(v, u);
    for (int i = 17; i >= 0; i --)
        if (d[u] - MASK(i) >= d[v]) u = pa[u][i];
    if (u == v) return u;
    for (int i = 17; i >= 0; i --)
        if (pa[u][i] != pa[v][i])
        {
            u = pa[u][i];
            v = pa[v][i];
        }
    return pa[u][0];
}

ll ans = 0;
int sum[N];

void dp(int u)
{
    for (int id : ar[u])
    {
        int v = e[id].other(u);
        if (v != pa[u][0])
        {
            dp(v);
            sum[u] += sum[v];
            ans += min(1LL * e[id].c1 * sum[v], 1LL * e[id].c2);
        }
    }
}

void solve(void)
{
    dfs(1);
    for (int i = 2; i <= n; i ++)
    {
        int k = lca(i - 1, i);
        sum[i] ++;
        sum[i - 1] ++;
        sum[k] -= 2;
    }
    dp(1);
    cout << ans;
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("shipping.inp", "r", stdin);
//freopen("shipping.out", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 3 ms 11356 KB Output is correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 2 ms 11424 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 3 ms 11364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 24764 KB Output is correct
2 Correct 66 ms 25904 KB Output is correct
3 Correct 80 ms 26964 KB Output is correct
4 Correct 93 ms 28500 KB Output is correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 66 ms 24712 KB Output is correct
7 Correct 44 ms 21044 KB Output is correct
8 Correct 70 ms 24632 KB Output is correct
9 Correct 48 ms 24452 KB Output is correct
10 Correct 50 ms 24172 KB Output is correct
11 Correct 50 ms 26708 KB Output is correct
12 Correct 52 ms 26708 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 3 ms 11356 KB Output is correct
3 Correct 3 ms 11356 KB Output is correct
4 Correct 3 ms 11356 KB Output is correct
5 Correct 3 ms 11356 KB Output is correct
6 Correct 2 ms 11424 KB Output is correct
7 Correct 3 ms 11356 KB Output is correct
8 Correct 3 ms 11356 KB Output is correct
9 Correct 3 ms 11364 KB Output is correct
10 Correct 64 ms 24764 KB Output is correct
11 Correct 66 ms 25904 KB Output is correct
12 Correct 80 ms 26964 KB Output is correct
13 Correct 93 ms 28500 KB Output is correct
14 Correct 3 ms 11356 KB Output is correct
15 Correct 66 ms 24712 KB Output is correct
16 Correct 44 ms 21044 KB Output is correct
17 Correct 70 ms 24632 KB Output is correct
18 Correct 48 ms 24452 KB Output is correct
19 Correct 50 ms 24172 KB Output is correct
20 Correct 50 ms 26708 KB Output is correct
21 Correct 52 ms 26708 KB Output is correct
22 Correct 82 ms 20760 KB Output is correct
23 Correct 47 ms 20340 KB Output is correct
24 Correct 64 ms 20816 KB Output is correct
25 Correct 3 ms 11356 KB Output is correct
26 Correct 24 ms 17000 KB Output is correct
27 Correct 56 ms 20308 KB Output is correct
28 Correct 52 ms 23644 KB Output is correct
29 Correct 57 ms 26684 KB Output is correct
30 Correct 53 ms 26708 KB Output is correct
31 Correct 3 ms 11352 KB Output is correct