Submission #1024038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024038		kustizus	Putovanje (COCI20_putovanje)	C++17	110 / 110	89 ms	37424 KiB

putovanje

/*---------------Nguyen Thanh Nam---------------*/
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define int long long int

using namespace std;

const long long inf = 1e+18;
// const int MOD=998244353;
const int MOD = 1e9 + 7;
const int N = 2e5;
int h[N + 5], pre[N + 5], pa[N + 5][20];
vector<int> g[N + 5];
void DFS(int i, int p)
{
    for (int j : g[i])
        if (j != p)
        {
            pa[j][0] = i;
            h[j] = h[i] + 1;
            for (int k = 1; k <= 17; k++)
                pa[j][k] = pa[pa[j][k - 1]][k - 1];
            DFS(j, i);
        }
}
void DFS1(int i, int p)
{
    for (int j : g[i])
        if (j != p)
        {
            DFS1(j, i);
            pre[i] += pre[j];
        }
}
int lca(int u, int v)
{
    if (h[u] < h[v])
        swap(u, v);
    for (int i = 17; i >= 0; i--)
        if (h[pa[u][i]] >= h[v])
            u = pa[u][i];
    if (u == v)
        return v;
    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];
}
void Solve()
{
    int n;
    cin >> n;
    struct Node
    {
        int u, v, x, y;
    };
    vector<Node> a(n - 1);
    for (Node &x : a)
    {
        cin >> x.u >> x.v >> x.x >> x.y;
        g[x.u].push_back(x.v);
        g[x.v].push_back(x.u);
    }
    h[1] = 1;
    DFS(1, 0);
    for (int i = 1; i < n; i++)
    {
        int u = lca(i, i + 1);
        if (u == i || u == i + 1)
        {
            pre[i * 2 + 1 - u]++;
            pre[u]--;
        }
        else
        {
            pre[i]++;
            pre[i + 1]++;
            pre[u] -= 2;
        }
    }
    DFS1(1, 0);
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int d = (h[a[i].u] > h[a[i].v] ? a[i].u : a[i].v);
        ans += min(pre[d] * a[i].x, a[i].y);
    }
    cout << ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--)
        Solve();
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
}

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