Submission #218146

#	Time	Username	Problem	Language	Result	Execution time	Memory
218146		Vimmer	Putovanje (COCI20_putovanje)	C++14	110 / 110	200 ms	71516 KiB

putovanje

#include <bits/stdc++.h>

#define N 200005
#define pb push_back
#define sz(x) ll(x.size())
#define P 31
#define F first
#define S second
#define MOD ll(1000000007)

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

using namespace std;

typedef long long ll;

ll t[N + N + N][20], n, in[N], out[N], h[N], dp[N], ans;

vector <pair <pair <ll, ll>, ll> > g[N];

vector <ll> vr;

void dfs(ll v, ll p)
{
    if (p != -1) h[v] = h[p] + 1;

    in[v] = sz(vr);

    vr.pb(v);

    for (auto it : g[v])
    {
        if (it.S == p) continue;

        dfs(it.S, v);

        vr.pb(v);
    }

    out[v] = sz(vr);

    vr.pb(v);
}

ll lca(ll x, ll y)
{
    if (in[x] > in[y]) swap(x, y);

    ll j = 0;

    while ((1 << (j + 1)) <= in[y] - in[x] + 1) j++;

    ll fr = t[in[x]][j];

    ll sc = t[in[y] - (1 << j) + 1][j];

    if (h[fr] > h[sc]) return sc;

    return fr;
}

ll rec(ll v, ll p, ll c1, ll c2)
{
    ll sm = 0;

    for (auto it : g[v])
    {
        if (it.S == p) continue;

        sm += rec(it.S, v, it.F.F, it.F.S);
    }

    sm += dp[v];

    if (v != 1) ans += min(sm * c1, c2);

    return sm;
}
int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (ll i = 1; i < n; i++)
    {
        ll x, y, c1, c2;

        cin >> x >> y >> c1 >> c2;

        g[x].pb({{c1, c2}, y});

        g[y].pb({{c1, c2}, x});
    }

    dfs(1, -1);

    for (ll i = 0; i < sz(vr); i++) t[i][0] = vr[i];

    for (ll j = 1; j < 20; j++)
        for (ll i = 0; i < sz(vr); i++)
        {
            ll x = t[i][j - 1];

            ll y = t[min(sz(vr) - 1, i + (1 << (j - 1)))][j - 1];

            if (h[x] > h[y]) t[i][j] = y; else t[i][j] = x;
        }

   for (ll i = 1; i < n; i++)
   {
       ll lc = lca(i, i + 1);

       dp[lc] -= 2;

       dp[i]++; dp[i + 1]++;
   }

   rec(1, -1, -1, -1);

   cout << ans << endl;
}

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