Submission #223309

#	Time	Username	Problem	Language	Result	Execution time	Memory
223309		rainy	Putovanje (COCI20_putovanje)	C++17	20 / 110	1096 ms	54508 KiB

putovanje

#include<bits/stdc++.h>
#define INF 2123456789
#define BINF 9123456789123456789
#define MAXN 200005
//#define DB
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pl> vpl;
int N,A,B,C1,C2;
map<ii,int> sp;
map<ii,int> mp;
map<ii,int> nt;
map<ii,int> tt;
vii el;
vi al[MAXN];
int p[MAXN][25],d[MAXN];

void root(int v,int par){
    p[v][0]=par;
    if(par==-1)d[v]=0;
    else d[v]=d[par]+1;
    for(int i:al[v]){
        if(i!=par)root(i,v);
    }
}

int lca(int a,int b){
    if(d[a]<d[b])swap(a,b);
    for(int k=log2(N);k>=0;k--)
        if(p[a][k]!=-1&&d[p[a][k]]>=d[b])
            a=p[a][k];
    if(a==b)return a;
    for(int k=log2(N);k>=0;k--){
        if(p[a][k]!=p[b][k])a=p[a][k],b=p[b][k];
    }
    return p[a][0];
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N-1;i++){
        scanf("%d%d%d%d",&A,&B,&C1,&C2);
        A--;B--;
        ii p1=ii(A,B),p2=ii(B,A);
        el.pb(ii(A,B));
        sp[p1]=sp[p2]=C1;
        mp[p1]=mp[p2]=C2;
        tt[p1]=tt[p2]=0;
        al[A].pb(B);al[B].pb(A);
    }
    root(0,-1);
    for(int k=1;k<23;k++){
        for(int i=0;i<N;i++){
            if(p[i][k-1]!=-1)
                p[i][k]=p[p[i][k-1]][k-1];
            else p[i][k]=-1;
        }
    }
    for(int i=0;i<N-1;i++){
        int aa=i,bb=i+1;
        #ifdef DB
        printf("%d -> %d\n",aa+1,bb+1);
        #endif // DB
        int anc=lca(aa,bb);
        while(aa!=anc){
            tt[ii(aa,p[aa][0])]++;
            #ifdef DB
            printf("%d-%d\n",aa+1,p[aa][0]+1);
            #endif // DB
            aa=p[aa][0];
        }
        while(bb!=anc){
            tt[ii(bb,p[bb][0])]++;
            #ifdef DB
            printf("%d-%d\n",bb+1,p[bb][0]+1);
            #endif // DB
            bb=p[bb][0];
        }
    }
    int ans=0;
    for(ii i:el){
        ii j=ii(i.second,i.first);
        int k=tt[i]+tt[j];
        if(k>0)ans+=min(k*sp[i],mp[i]);
        #ifdef DB
        printf("%d->%d for %d time(s) costs $%d\n",i.first,i.second,k,ans);
        #endif
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
putovanje.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d",&A,&B,&C1,&C2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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