Submission #864080

#	Time	Username	Problem	Language	Result	Execution time	Memory
864080		amogususus	Putovanje (COCI20_putovanje)	C++17	110 / 110	67 ms	37764 KiB

putovanje

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=2e5+69;
const int mod=998244353;
ll n,f[maxN],tin[maxN],tout[maxN],timer=0,up[maxN][20];
struct edg{ll v,w,z;};
vector<edg> adj[maxN];
void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i < 20; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
    for (auto [u,_,__] : adj[v])if (u != p)dfs(u, v);
    tout[v] = ++timer;
}
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = 19; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
ll pfs[maxN];
ll r=0;
void dfss(ll u,ll p=0){
    for(auto [v,w,c]:adj[u]){
        if(v==p)continue;
        dfss(v,u);
        r+=min(pfs[v]*w,c);
        pfs[u]+=pfs[v];
    }
}
void Enter(){
    cin>>n;
    for(int i=1;i<n;i++){
        ll u,v,w,c;cin>>u>>v>>w>>c;
        adj[u].pb({v,w,c});
        adj[v].pb({u,w,c});
    }
    dfs(1,1);
    for(int i=1;i<n;i++){
        ll x=lca(i,i+1);
        pfs[i]++;
        pfs[i+1]++;
        pfs[x]-=2;
    }
    dfss(1);
    cout<<r;
}
signed main(){
    //open("zzz");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

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