Submission #227318

#	Time	Username	Problem	Language	Result	Execution time	Memory
227318		papa	Putovanje (COCI20_putovanje)	C++14	0 / 110	70 ms	15736 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct gr
{
    int u,a,b;
};

int n;
vector<gr> adj[200005];
ll dp[200005];
int sz[200005];
int ma[200005];
int mi[200005];

int siz(int u,int p)
{
    sz[u] = 1;
    for(gr gg : adj[u])
    {
        if(gg.u==p) continue;
        sz[u]+=siz(gg.u,u);
    }
    return sz[u];
}

int maks(int u,int p)
{
    ma[u] = u;
    for(gr gg : adj[u])
    {
        if(gg.u==p) continue;
        ma[u]=max(ma[u],maks(gg.u,u));
    }
    return ma[u];
}

int mini(int u,int p)
{
    mi[u] = u;
    for(gr gg : adj[u])
    {
        if(gg.u==p) continue;
        mi[u]=min(mi[u],mini(gg.u,u));
    }
    return mi[u];
}

ll resi(int u,int p)
{
    dp[u] = 0LL;
    ll k;
    for(gr gg : adj[u])
    {
        int v = gg.u;
        int a = gg.a;
        int b = gg.b;
        if(v==p) continue;
        k = resi(v,u);
        dp[u]+=dp[v] + min(k*a,(ll)b);
    }

    k = 2LL*(ma[u]-mi[u]+1-sz[u]+1);
    if(ma[u]==n) k--;
    return k;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);

    cin >> n;

    for(int i=1;i<n;i++)
    {
        gr g;
        int u,v;
        cin >> u >> v >> g.a >> g.b;
        g.u=v;
        adj[u].push_back(g);
        g.u=u;
        adj[v].push_back(g);
    }

    sz[1] = siz(1,-1);
    ma[1] = maks(1,-1);
    mi[1] = mini(1,-1);
    
   // for(int i=1;i<=n;i++) cout << sz[i] << " ";
   // cout << "\n";
   // for(int i=1;i<=n;i++) cout << mi[i] << " ";
   // cout << "\n";
   // for(int i=1;i<=n;i++) cout << ma[i] << " ";
   // cout << "\n";
    
    resi(1,-1);

    cout << dp[1];

    return 0;
}

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