oj.uz

답안 #206729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206729 2020-03-04T21:36:22 Z rzbt Putovanje (COCI20_putovanje) C++14
110 / 110
 330 ms 37752 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 200005
typedef long long ll;

using namespace std;
ll n,res,res2;
vector<pair<ll,pair<ll,ll> > > niz[MAXN];
ll dubina[MAXN];
ll predak[MAXN][21];
ll dodaj[MAXN],oduzmi[MAXN];

void lca(ll a,ll b){
    if(dubina[b]>dubina[a])swap(a,b);
    ll pa=a,pb=b;
    for(ll i=20;i>=0;i--){
        if(dubina[predak[a][i]]>=dubina[b]){
            a=predak[a][i];
        }
    }

    if(a==b){
        a=pa;
        for(ll i=20;i>=0;i--){
        if(dubina[predak[a][i]]>dubina[b]){
            a=predak[a][i];
        }
    }
        dodaj[a]++;
        oduzmi[pa]++;
        return;
    }
    //printf("  %lld %lld    %lld %lld\n",a,pa,b,pb);
    for(ll i=20;i>=0;i--){
        if(predak[a][i]!=predak[b][i]){
            a=predak[a][i];
            b=predak[b][i];
        }
    }

    dodaj[a]++;
    dodaj[b]++;
    oduzmi[pa]++;
    oduzmi[pb]++;


}
void dfsI(ll t,ll o,ll h){
    dubina[t]=h;
    predak[t][0]=o;
    for(auto x:niz[t]){
        if(x.F==o)continue;
        dfsI(x.F,t,h+1);
    }
}
ll tren=0;
int dfs(ll t,ll o ,ll c1,ll cv){

    int xyz=oduzmi[t];
    //printf("  %lld    %lld  %lld\n",t,tren*c1,cv);
    for(auto x:niz[t])
        if(x.F!=o)
            xyz+=dfs(x.F,t,x.S.F,x.S.S);
    res+=min(xyz*c1,cv);
    xyz-=dodaj[t];
    return xyz;
}



int main()
{
    scanf("%lld", &n);
    for(ll i=1;i<n;i++){
        ll t1,t2,c1,c2;
        scanf("%lld %lld %lld %lld", &t1, &t2, &c1, &c2);
        niz[t1].pb(mp(t2,mp(c1,c2)));
        niz[t2].pb(mp(t1,mp(c1,c2)));
    }
    dfsI(1,0,1);
    for(ll j=1;j<=20;j++){
        for(ll i=1;i<=n;i++){
            predak[i][j]=predak[predak[i][j-1]][j-1];
        }
    }
    for(ll i=1;i<n;i++){
        lca(i,i+1);
    }
    dfs(1,0,0,0);
    printf("%lld",res);
    return 0;
}

Compilation message

putovanje.cpp: In function 'int main()':
putovanje.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
putovanje.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld %lld", &t1, &t2, &c1, &c2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 10 ms 5624 KB Output is correct
4 Correct 11 ms 5624 KB Output is correct
5 Correct 10 ms 5624 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5240 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 31448 KB Output is correct
2 Correct 245 ms 34520 KB Output is correct
3 Correct 266 ms 37728 KB Output is correct
4 Correct 330 ms 37752 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 235 ms 32352 KB Output is correct
7 Correct 157 ms 25004 KB Output is correct
8 Correct 267 ms 33196 KB Output is correct
9 Correct 138 ms 34040 KB Output is correct
10 Correct 120 ms 33144 KB Output is correct
11 Correct 146 ms 35608 KB Output is correct
12 Correct 144 ms 35704 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 9 ms 5496 KB Output is correct
3 Correct 10 ms 5624 KB Output is correct
4 Correct 11 ms 5624 KB Output is correct
5 Correct 10 ms 5624 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5240 KB Output is correct
8 Correct 9 ms 5368 KB Output is correct
9 Correct 9 ms 5496 KB Output is correct
10 Correct 242 ms 31448 KB Output is correct
11 Correct 245 ms 34520 KB Output is correct
12 Correct 266 ms 37728 KB Output is correct
13 Correct 330 ms 37752 KB Output is correct
14 Correct 8 ms 5240 KB Output is correct
15 Correct 235 ms 32352 KB Output is correct
16 Correct 157 ms 25004 KB Output is correct
17 Correct 267 ms 33196 KB Output is correct
18 Correct 138 ms 34040 KB Output is correct
19 Correct 120 ms 33144 KB Output is correct
20 Correct 146 ms 35608 KB Output is correct
21 Correct 144 ms 35704 KB Output is correct
22 Correct 191 ms 31480 KB Output is correct
23 Correct 187 ms 28536 KB Output is correct
24 Correct 182 ms 31096 KB Output is correct
25 Correct 9 ms 5368 KB Output is correct
26 Correct 68 ms 17016 KB Output is correct
27 Correct 160 ms 27384 KB Output is correct
28 Correct 108 ms 30584 KB Output is correct
29 Correct 128 ms 35704 KB Output is correct
30 Correct 133 ms 35448 KB Output is correct
31 Correct 10 ms 5624 KB Output is correct