Submission #1177639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177639		Warinchai	Putovanje (COCI20_putovanje)	C++20	110 / 110	202 ms	33224 KiB

putovanje

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int,int>>adj[100005];
vector<pair<int,int>>edge;
int val[100005];
int p[20][100005];
int lv[100005];
int freq[100005];
int eid[100005];

int lca(int a,int b){
    if(lv[b]>lv[a])swap(a,b);
    for(int i=19;i>=0;i--)if(lv[p[i][a]]>=lv[b])a=p[i][a];
    if(a==b)return a;
    for(int i=19;i>=0;i--)if(p[i][a]!=p[i][b])a=p[i][a],b=p[i][b];
    return p[0][a];
}

void dfs(int u,int pa){
    p[0][u]=pa;
    lv[u]=lv[pa]+1;
    for(int i=1;i<20;i++)p[i][u]=p[i-1][p[i-1][u]];
    for(auto x:adj[u])if(x.first!=pa){
        dfs(x.first,u);
        eid[x.first]=x.second;
    }
}

void efs(int u,int pa){
    for(auto x:adj[u])if(x.first!=pa){
        efs(x.first,u);
        val[u]+=val[x.first];
    }
    //cerr<<"u:"<<u<<" "<<val[u]<<"\n";
    if(u!=1)freq[eid[u]]=val[u];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b,c,d;cin>>a>>b>>c>>d;
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
        edge.push_back({c,d});
    }
    dfs(1,0);
    for(int i=1;i<n;i++){
        int x=lca(i,i+1);
        val[x]-=2;
        val[i]++;
        val[i+1]++;
    }
    efs(1,0);
    int ans=0;
    for(int i=0;i<n;i++){
        int mn=min(edge[i].second,edge[i].first*freq[i]);
        ans+=mn;
    }
    cout<<ans;
}

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