Submission #401906

#	Time	Username	Problem	Language	Result	Execution time	Memory
401906		fadi57	Putovanje (COCI20_putovanje)	C++14	110 / 110	274 ms	28736 KiB

putovanje

#include<bits/stdc++.h>
using namespace std;
const int mx=200002;
typedef long long ll;
int inf=1e9+10;
const int mod=1e9+7;
int n,m;



vector<pair<int,pair<ll,ll>>> adj[200002];

int dp[200001][22];
int depth[mx];
void dfs(int node,int p){
dp[node][0]=p;
   depth[node]=depth[p]+1;
for(int i=1;i<=20;i++){
    dp[node][i]=dp[dp[node][i-1]][i-1];
}
for(auto it:adj[node]){
    if(it.first!=p){

        dfs(it.first,node);
    }
}

return;
 }
 int kth(int node,int k){


 for(int i=0;i<20;i++){

    if((1<<i)&k){
           // cout<<"TEST "<<i;
        node=dp[node][i];
    }
 }
 return node;


  }
 int lca(int a,int b){

 if(depth[a]<depth[b]){
    swap(a,b);
 }

 a=kth(a,depth[a]-depth[b]);

 if(a==b){return a;}

 for(int i=19;i>=0;i--){

    int aa=dp[a][i];
    int bb=dp[b][i];
    if(aa==bb){
        continue;
    }else{

    a=aa;b=bb;

    }
 }
 return dp[a][0];
  }
  int dp2[200002];
  ll ans;
  int dfs2(int node,int p){
ll sum=dp2[node];

  for(auto it:adj[node]){

    if(it.first==p){continue;}



ll sum2=0;
   sum2+=dfs2(it.first,node);
    sum+=sum2;
    ans+=min(1LL*it.second.first*sum2,it.second.second);
  }

  return sum;


  }

int main(){
cin>>n;

 for(int i=0;i<n-1;i++){
        int x,y,c1,c2;
    cin>>x>>y>>c1>>c2;
    adj[x].push_back({y,{c1,c2}});
     adj[y].push_back({x,{c1,c2}});
 }
dfs(1,0);

//cout<<lca(3,5);

 for(int i=1;i<n;i++){

    dp2[i]++;

    dp2[i+1]++;

    int x=lca(i,i+1);
  dp2[x]-=2;

 }
 dfs2(1,-1);
cout<<ans;
 }

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