Submission #857822

#	Time	Username	Problem	Language	Result	Execution time	Memory
857822		hct_2so1	Putovanje (COCI20_putovanje)	C++17	110 / 110	93 ms	28500 KiB

putovanje

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65