Submission #223194

#	Time	Username	Problem	Language	Result	Execution time	Memory
223194		tqbfjotld	Putovanje (COCI20_putovanje)	C++14	110 / 110	152 ms	19448 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
#define MAX_N 200005

vector<pair<int,int> >adjl[200005];
int p[200005];
int h[200005];
int head[200005];
int pos[200005];
long long fenwick[MAX_N];
int cur = 0;
long long o1[200005];
long long o2[200005];
int val[200005];
int heavy[200005];

void update(int po, long long val){
    //printf("upd %d with %d\n",po,val);
    while (po<MAX_N){
        fenwick[po] += val;
        po += (po&(-po));
    }
}

long long query(int a){
    long long ans = 0;
    while (a>0){
        ans += fenwick[a];
        a -= (a&(-a));
    }
    return ans; //I NEED TO STOP FORGETTING THIS
}

long long query(int a, int b){
    return query(b)-query(a-1);
}


int dfs(int node, int parent, int height){
    h[node] = height;
    p[node] = parent;

    int cursize = 1;
    int maxsize = -1;
    for (auto x : adjl[node]){
        if (x.first==parent) {
            val[node] = x.second;
            continue;
        }
        int t = dfs(x.first,node,height+1);
        if (t>maxsize){
            heavy[node] = x.first;
            maxsize = t;
        }
        cursize+=t;
    }
    return cursize;
}

void decomp(int node, int he){
    head[node] = he;
    pos[node] = cur;
    cur++;
    if (heavy[node]!=-1) decomp(heavy[node],he);
    for (auto x : adjl[node]){
        if (x.first == p[node]) continue;
        if (x.first == heavy[node]) continue;
        decomp(x.first,x.first);
    }

}

int main(){
    int n;
    scanf("%d",&n);
    for (int x = 0; x<n-1; x++){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        adjl[a].push_back({b,x});
        adjl[b].push_back({a,x});
        o1[x] = d;
        o2[x] = c;
    }
    memset(heavy,-1,sizeof(heavy));
    dfs(1,-1,0);
    decomp(1,1);
    for (int x = 2; x<=n; x++){
        int a = x-1;
        int b = x;
        while (head[a]!=head[b]){
            if (h[head[a]]<h[head[b]]) {
                int t = a;
                a = b;
                b = t;
            }
            update(pos[head[a]],1);
            update(pos[a]+1,-1);
            a = p[head[a]];
        }
        if (a!=b){
            update(min(pos[a],pos[b])+1,1);
            update(max(pos[a],pos[b])+1,-1);
        }
    }
    long long ans = 0;
    for (int x = 2; x<=n; x++){
        long long option1 = o1[val[x]];
        long long option2 = o2[val[x]]*query(pos[x]);
        ans += min(option1,option2);
    }
    printf("%lld",ans);

}

Compilation message (stderr)

putovanje.cpp: In function 'int main()':
putovanje.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
putovanje.cpp:78: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,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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