Submission #401864

#	Time	Username	Problem	Language	Result	Execution time	Memory
401864		fadi57	Putovanje (COCI20_putovanje)	C++14	0 / 110	157 ms	21408 KiB

putovanje

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


 int visited[100002];
vector<pair<int,pair<ll,ll>>> adj[100002];
int in[mx];
int dp[2000001][20];
int depth[mx];
void dfs(int node,int p){
dp[node][0]=p;
//cout<<dp[4][0]<<" "<<p<<endl;
for(int i=1;i<=20;i++){
    dp[node][i]=dp[dp[i][i-1]][i-1];
}
for(auto it:adj[node]){
    if(it.first!=p){
            depth[it.first]=depth[node]+1;
        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;}
 //cout<<88;
 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(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,-1);

//cout<<lca(2,4);
 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;
 }

Compilation message (stderr)

putovanje.cpp: In function 'void dfs(int, int)':
putovanje.cpp:19:16: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   19 |     dp[node][i]=dp[dp[i][i-1]][i-1];
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
putovanje.cpp:18:14: note: within this loop
   18 | for(int i=1;i<=20;i++){
      |             ~^~~~

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