Submission #1112286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112286		ezzzay	Putovanje (COCI20_putovanje)	C++14	0 / 110	162 ms	81508 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<pair<int,pair<int,int> > >v [N] ;
set< pair<int,int>>st[N];
int ans=0;
void merge(int a, int b){
    for(auto p:st[b]){
        auto it=st[a].upper_bound(p);
        if(it!=st[a].end()){
            auto k= *it;
            if(k.ff=p.ss+1){
                st[a].erase(it);
                st[a].insert({p.ff,k.ss});
                continue;
            }
        }
        if(it!=st[a].begin()){
            it--;
            auto k= *it;
            if(k.ss+1==p.ff){
                st[a].erase(it);
                st[a].insert({k.ff,p.ss});
                continue;
            }
        }
        st[a].insert(p);
        
        
    }
}
void dfs(int a, int p){
    for(auto k:v[a]){
        int b=k.ff;
        int c1=k.ss.ff,c2=k.ss.ss;
        if(b==p)continue;
        dfs(b,a);
        
        int f=st[b].size();
     //   cout<<a<<" "<<b<<" :: "<<f<<endl;
        ans+= min(c2,f*c1);
    }
    st[a].insert({a,a});
    for(auto k:v[a]){
        int b=k.ff;
        if(b==p)continue;
        merge(a,b);
    }
  //  cout<<a<<" :: "<<endl;
    //for(auto k:st[a]){
     //   cout<<k.ff<<" "<<k.ss<<endl;
   // }
   // cout<<endl;
}
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c1,c2;
        cin>>a>>b>>c1>>c2;
        v[a].pb({b,{c1,c2}});
        v[b].pb({a,{c1,c2}});
    }
    
    dfs(1,0);
    cout<<ans;
}

Compilation message (stderr)

putovanje.cpp: In function 'void merge(long long int, long long int)':
putovanje.cpp:16:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   16 |             if(k.ff=p.ss+1){
      |                ~~~~^~~~~~~

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