Submission #499380

#	Time	Username	Problem	Language	Result	Execution time	Memory
499380		Neos	Putovanje (COCI20_putovanje)	C++14	110 / 110	142 ms	74160 KiB

putovanje

#include <bits/stdc++.h>

#define pb emplace_back
#define all(x) x.begin(),x.end()
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll,ll> pii;
const int maxN = 1e6+1;
const int inf = 1e9;
const int MOD = 1e9+7;

struct node{
    int v;
    ll w,c;
    node(){};
    node(int v,ll w,ll c){
        this->v=v;
        this->w=w;
        this->c=c;
    }
};

int n;
vector<node> a[maxN];
int l=20;
int up[maxN][21];
int in[maxN],out[maxN],timer=0;
ll pf[maxN];
pii tr[maxN];
int mxh=0;
ll ans=0;
vector<int> d[maxN];

bool anc(int p,int s){
    return in[p]<=in[s]&&out[p]>=out[s];
}

int lca(int u,int v){
    if(anc(u,v)) return u;
    if(anc(v,u)) return v;
    for(int i=l;i>=0;i--){
        if(!anc(up[u][i],v)) u=up[u][i];
    }return up[u][0];
}

void dfs(int x,int pre,int h){
    in[x]=timer++;
    up[x][0]=pre;
    mxh=max(mxh,h);
    d[h].pb(x);
    for(int i=1;i<=l;i++){
        up[x][i]=up[up[x][i-1]][i-1];
    }
    for(auto i:a[x]){
        if(i.v==pre) continue;
        tr[i.v]=pii(i.w,i.c);
        dfs(i.v,x,h+1);
    }
    out[x]=timer++;
}

void buildPF(){
    for(int i=1;i<n;i++){
        int x=lca(i,i+1);
        if(x==i){
            pf[i+1]++;
            pf[x]--;
        }else if(x==i+1){
            pf[i]++;
            pf[x]--;
        }else{
            pf[i]++;
            pf[i+1]++;
            pf[x]-=2;
        }
    }
    for(int i=mxh;i>0;i--){
        for(int x:d[i]){
            ans+=min(tr[x].fi*pf[x],tr[x].se);
            pf[up[x][0]]+=pf[x];
        }
    }
}

int main()
{
    fastio;
    int u,v,w,c;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>u>>v>>w>>c;
        a[u].pb(node(v,w,c));
        a[v].pb(node(u,w,c));
    }dfs(1,1,0);
    buildPF();
    cout<<ans<<endl;
}

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