Submission #217223

#	Time	Username	Problem	Language	Result	Execution time	Memory
217223		Vimmer	Putovanje (COCI20_putovanje)	C++14	20 / 110	1091 ms	17632 KiB

putovanje

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 200005
#define M ll(1000000007)

using namespace std;

typedef long long ll;


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

ll ans;

int n, in[N], out[N], tp;

void dfs(int v, int p, set <int> &vr, ll c1, ll c2)
{
    for (auto it : g[v])
    {
        if (it.F.F == p) continue;

        set <int> pt; pt.clear();

        dfs(it.F.F, v, pt, it.F.S, it.S);

        for (auto itr : pt) vr.insert(itr);
    }

    vr.insert(v);

    if (v != 1)
    {
        ll kol = 0, lst = -1;

        for (auto it : vr)
        {
            if (lst + 1 != it) kol += 2;

            lst = it;

            if (it == n) kol--;
        }

        ans += min(c1 * kol, c2);
    }

}

void rec(int v, int p)
{
    in[v] = tp++;

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

        rec(it.F.F, v);
    }

    out[v] = tp++;
}
void dfser(int v, int p, vector <int> &vr, ll c1, ll c2)
{


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

        vector <int> gr; gr.clear();

        dfser(it.F.F, v, gr, c1, c2);

        for (auto itr : gr) if (itr < in[v] || out[v] < itr) vr.pb(itr);
    }

    if (v != 1)
    {
        if (v != n && (in[v + 1] < in[v] || out[v] < in[v + 1])) vr.pb(in[v + 1]);

        ll kol = 2 + sz(vr) * 2;

        if (in[v] <= in[n] && out[n] <= out[v]) kol--;

        ans += max(c1 * kol, c2);
    }

}
int main()
{
    //freopen("mining.in","r",stdin); freopen("mining.out","w",stdout);
    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({{y, c1}, c2});

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

    if (n <= 2000)
    {
        set <int> st; st.clear();

        dfs(1, -1, st, -1, -1);
    }
    else
    {
        rec(1, -1);

        vector <int> gr; gr.clear();

        dfser(1, -1, gr, -1, -1);
    }
    cout << ans << endl;
}

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