oj.uz

답안 #854474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854474 2023-09-27T17:25:38 Z vjudge1 Sjekira (COCI20_sjekira) C++17
50 / 110
 128 ms 34132 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64

#define ONLINE_JUDGE
void solve(int n) {
    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];

    set <int> adj[n +1];
    for(int i = 1; i <= n -1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace(v);
        adj[v].emplace(u);
    }

    function <int(int, int)> dfsMax = [&](int node, int par) -> int {
        int ind = node;
        for(const int &child : adj[node]) {
            if(child != par) {
                int g = dfsMax(child, node);
                //cerr << child << " " << node << " :: " << g << "\n";
                if(vec[g] >= vec[ind]) {
                    ind = g;
                }
            }
        }

        return ind;
    };

    int res = 0;
    function <void(int)> dfsAns = [&](int node) -> void {
        //cerr << "# " << node << "\n";
        int cev = 0;
        vector <int> vvec;
        for(const int &child : adj[node]) {
            cev += vec[node];
            int g = dfsMax(child, node);
            cerr << child << " " << node << " :: " << g << "\n";
            cev += vec[g];
            adj[child].erase(node);
            vvec.emplace_back(child);
        }

        adj[node].clear();

        for(int &i : vvec) {
            dfsAns(dfsMax(i, node));
        }

        //cerr << node << " " << cev << "\n";
        res += cev;
    };

    dfsAns(dfsMax(1, 0));

    cout << res;
    
    return;
}

void solve2(int n) {
    vector <int> vec(n +5, 0);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];

    set <int> adj[n +1];
    for(int i = 1; i <= n -1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace(v);
        adj[v].emplace(u);
    }

    auto f = [&](int a, int b) -> int {
        if(vec[a] <= vec[b]) {
            return (1 <= b && b <= n) ? b : a;
        }
        return a;
    };
    
    vector <int> ST((n + 10) * 4);
    function <int(int, int, int)> build = [&](int node, int l, int r) -> int {
        if(l == r) {
            return ST[node] = r;
        }

        int mid = (l + r) / 2;
        return ST[node] = f(build(node * 2, l, mid), build(node * 2 +1, mid +1, r));
    };

    build(1, 1, n + 5);
    
    function <int(int, int, int, int, int)> get = [&](int node, int l, int r, int ql, int qr) -> int {
        if(r < ql || qr < l) {
            return 0;
        } else if(ql <= l && r <= qr) {
            return ST[node];
        }

        int mid = (l + r) / 2;
        return f(get(node * 2, l, mid, ql, qr), get(node * 2 +1, mid +1, r, ql, qr));
    };

    int ans = 0;
    function <void(int, int)> dfs = [&](int l, int r) -> void {
        //cerr << l << " " << r << "\n";
        if(r <= l) {
            return;
        }

        int g = get(1, 1, n + 5, l, r);
        //cerr << l << " " << r << " " << g << "\n";
        int cev = 0;
        cev += vec[get(1, 1, n + 5, l, g -1)];
        cev += vec[get(1, 1, n + 5, g +1, r)];
        cev += vec[g] * ((g != r) + (g != l));

        ans += cev;

        //cerr << l << " " << r << " :: " << cev << "\n";

        dfs(l, g -1);
        dfs(g +1, r);
    };

    dfs(1, n);
    cout << ans;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        int n;
        cin >> n;
        if(n <= 1000)
            solve(n);
        else 
            solve2(n);
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 14940 KB Output is correct
2 Correct 50 ms 11352 KB Output is correct
3 Correct 49 ms 11096 KB Output is correct
4 Correct 54 ms 12376 KB Output is correct
5 Correct 97 ms 18456 KB Output is correct
6 Correct 128 ms 31684 KB Output is correct
7 Correct 105 ms 26704 KB Output is correct
8 Correct 95 ms 24144 KB Output is correct
9 Correct 68 ms 17132 KB Output is correct
10 Correct 119 ms 34132 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 8 ms 604 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Correct 10 ms 420 KB Output is correct
10 Correct 11 ms 604 KB Output is correct

Subtask #4
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 67 ms 14940 KB Output is correct
7 Correct 50 ms 11352 KB Output is correct
8 Correct 49 ms 11096 KB Output is correct
9 Correct 54 ms 12376 KB Output is correct
10 Correct 97 ms 18456 KB Output is correct
11 Correct 128 ms 31684 KB Output is correct
12 Correct 105 ms 26704 KB Output is correct
13 Correct 95 ms 24144 KB Output is correct
14 Correct 68 ms 17132 KB Output is correct
15 Correct 119 ms 34132 KB Output is correct
16 Correct 9 ms 604 KB Output is correct
17 Correct 8 ms 604 KB Output is correct
18 Correct 6 ms 348 KB Output is correct
19 Correct 10 ms 420 KB Output is correct
20 Correct 11 ms 604 KB Output is correct
21 Incorrect 20 ms 4956 KB Output isn't correct
22 Halted 0 ms 0 KB -