Submission #937039

#	Time	Username	Problem	Language	Result	Execution time	Memory
937039		sleepntsheep	Putovanje (COCI20_putovanje)	C++17	110 / 110	70 ms	18000 KiB

putovanje

#include<stdio.h>
#include<stdlib.h>
#define N 200005
long long z,run;
int n,ff[N],dd[N],pp[N],jj[N],e[N<<1][4],ne,h[N],tin[N],tout[N],timer=1;
void link(int u,int v,int c1,int c2){
    e[++ne][0]=v,e[ne][1]=c1,e[ne][2]=c2,e[ne][3]=h[u],h[u]=ne;
}
void dfs(int u,int p){
    dd[u]=dd[pp[u]=p]+1;
    jj[u]=(dd[p]-dd[jj[p]]==dd[jj[p]]-dd[jj[jj[p]]])?jj[jj[p]]:p;
    tin[u]=timer++;
    for(int v,j=h[u];j;j=e[j][3])if((v=e[j][0])-p){
        dfs(v,u);
    }
    tout[u]=timer++;
}
int lca(int u,int v){
    if(dd[v]<dd[u])return lca(v,u);
    while(dd[v]>dd[u])
        v=dd[jj[v]]>=dd[u]?jj[v]:pp[v];
    while(u-v)
        if(jj[u]!=jj[v])u=jj[u],v=jj[v];
        else u=pp[u],v=pp[v];
    return u;
}
void dfs2(int u,int p){
    for(int v,j=h[u];j;j=e[j][3])if((v=e[j][0])-p){
        dfs2(v,u);
        long long tk=e[j][2],fr=0;
        fr=ff[tout[v]]-ff[tin[v]-1];
        if(e[j][1]*1ll*fr<tk)tk=fr*1ll*e[j][1];
        z+=tk;
    }
}
int main(){
    scanf("%d",&n);
    for(int a,b,c,d,i=1;i<n;++i) scanf("%d%d%d%d",&a,&b,&c,&d), link(a,b,c,d),link(b,a,c,d);
    dfs(1,1);
    for(int a,i=1;i<n;++i)a=lca(i,i+1),++ff[tin[i]],++ff[tin[i+1]],ff[tin[a]]-=2;
    for(int i=1;i<timer;++i)ff[i]+=ff[i-1];
    dfs2(1,1);
    printf("%lld",z);
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
putovanje.cpp:38:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     for(int a,b,c,d,i=1;i<n;++i) scanf("%d%d%d%d",&a,&b,&c,&d), link(a,b,c,d),link(b,a,c,d);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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