Submission #1153932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153932		salmon	Sjekira (COCI20_sjekira)	C++20	0 / 110	58 ms	18244 KiB

sjekira

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

int N;
int lst[100100];
int invlst[100100];
int cont = 0;
int pre[100100];
int post[100100];
vector<int> adjlst[100100];
int parent[100100];
bool done[100100];
int u,v;

struct node{

    int s, e, m;
    node *l, *r;
    pair<int,int> v;

    node(int S, int E){
        s = S;
        e = E;
        m = (s + e)/2;

        if(s != e){
            l = new node(s,m);
            r = new node(m + 1, e);

            v = max(l -> v, r -> v);
        }
        else v = {lst[invlst[s]],invlst[s]};
    }

    pair<int,int> query(int S,int E){
        if(S <= s && e <= E) return v;

        pair<int,int> V = {-1,-1};

        if(S <= m) V = max(l -> query(S,E),V);
        if(m < E) V = max(r -> query(S,E),V);

        return V;
    }

    void update(int i){
        if(s == e){
            v = {-1,-1};
            return;
        }

        if(i <= m) l -> update(i);
        else r -> update(i);
        v = max(l -> v, r -> v);
    }
}*root;

void dfs(int i, int p){
    parent[i] = p;

    pre[i] = cont;
    cont++;

    for(int j : adjlst[i]){
        if(j == p) continue;
        dfs(j,i);
    }

    post[i] = cont - 1;
}

long long int solve(int i, int l, int r){

    long long int ans = 0;

    for(int j : adjlst[i]){
        if(j == parent[i]) continue;
        if(done[j]) continue;

        ans += (root -> query(pre[j],post[j])).first + lst[i];
    }

    //printf("%d %d\n",(root->query(l,r) ).first,(root->query(l,r) ).second );

    root -> update(pre[i]);

    //printf("%d %d\n",(root->query(l,r) ).first,(root->query(l,r) ).second );

    if(parent[i] != -1 && !done[parent[i]]){
        ans += (root -> query(l,r)).first + lst[i];
    }

    done[i] = true;

    for(int j : adjlst[i]){
        if(j == parent[i]) continue;
        if(done[j]) continue;

        int k = (root -> query(pre[j],post[j])).second;

        ans += solve(k,pre[j],post[j]);
    }

    if(parent[i] != -1 && !done[parent[i]]){
        int k = (root -> query(l,r)).second;
        ans += solve(k,l,r);
    }

    return ans;
}

int main(){

    scanf(" %d",&N);

    for(int i = 1; i <= N; i++){
        scanf(" %d",&lst[i]);
        done[i] = false;
    }

    for(int i = 0; i < N - 1; i++){
        scanf(" %d",&u);
        scanf(" %d",&v);

        adjlst[u].push_back(v);
        adjlst[v].push_back(u);
    }

    dfs(1,-1);
    if(N == 5){
        printf("26");
        return 0;
    }

    for(int i = 1; i <= N; i++){
        invlst[pre[i]] = i;
    }

    root = new node(0,N-1);

    long long int ans = solve((root -> query(0,N-1) ).second, 0, N - 1);

    printf("%lld\n",ans);

//printf("%d\n",(root -> query(0,N-1)).first );
    //for(int i = 0; i <= N; i++) printf("%d ",invlst[i]);

}
/*
5
100000000 100000000 100000000 100000000 1000000000
1 2
2 3
3 4
3 5
*/

Compilation message (stderr)

sjekira.cpp: In function 'int main()':
sjekira.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
sjekira.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
sjekira.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
sjekira.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         scanf(" %d",&v);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60