oj.uz

Submission #442038

# Submission time Handle Problem Language Result Execution time Memory
442038 2021-07-06T20:01:36 Z Abrar_Al_Samit Putovanje (COCI20_putovanje) C++17
110 / 110
 187 ms 49896 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define debug(x) cerr << '[' << (#x) << "] = " << x << '\n';

template<class T> using ordered_set = tree<T, null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int maxn = 2e5 + 5;

//https://oj.uz/problem/view/COCI20_putovanje

struct Edge{
    long long to;
    long long single, multi;
};

vector<Edge>g[maxn];
long long ans = 0, sub[maxn];
int tin[maxn], tout[maxn], timer, l;
vector<vector<int>>up(maxn, vector<int>(20));
void dfs(int node, int parent, Edge to_parent) {
    for(Edge e : g[node]) {
        if(e.to!=parent) {
            dfs(e.to, node, e);
            sub[node] += sub[e.to];
        }
    }
    if(parent!=0) ans += min(sub[node]*to_parent.single, to_parent.multi);
}
void dfs2(int node, int parent) {
    tin[node] = timer++;
    up[node][0] = parent;

    for(int i=1; i<=l; ++i) {
        up[node][i] = up[up[node][i-1]][i-1];
    }
    for(Edge e : g[node]) {
        if(e.to!=parent) dfs2(e.to, node);
    }
    tout[node] = timer++;
}
void PlayGround() {
    int n; cin >> n;
    l = log2(n) + 2;
    for(int i=1; i<n; ++i) {
        long long u, v, c, cc; cin >> u >> v >> c >> cc;
        Edge e = {v, c, cc};
        g[u].emplace_back(e);
        e.to = u;
        g[v].emplace_back(e);
    }
    dfs2(1, 1);
    auto is_ancestor = [=] (int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    };
    auto getLCA = [=] (int u, int v) {
        if(is_ancestor(u, v))
            return u;
        if(is_ancestor(v, u))
            return v;
        for(int i=l; i>=0; --i) {
            if(!is_ancestor(up[u][i], v))
                u = up[u][i];
        }
        return up[u][0];
    };
    for(int i=1; i<n; ++i) {
        int lca = getLCA(i, i+1);
        auto update = [&] (int u, int v) {
            sub[u]++, sub[v]--;
        };
        update(i, lca);
        update(i+1, lca);
    }
    Edge e = {0, 0, 0};
    dfs(1, 0, e);
    cout << ans << '\n';

    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
} 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    // #endif
    PlayGround();

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28492 KB Output is correct
2 Correct 24 ms 28660 KB Output is correct
3 Correct 29 ms 28620 KB Output is correct
4 Correct 28 ms 28656 KB Output is correct
5 Correct 25 ms 28684 KB Output is correct
6 Correct 23 ms 28464 KB Output is correct
7 Correct 22 ms 28560 KB Output is correct
8 Correct 24 ms 28636 KB Output is correct
9 Correct 24 ms 28624 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 45068 KB Output is correct
2 Correct 179 ms 47088 KB Output is correct
3 Correct 183 ms 49896 KB Output is correct
4 Correct 187 ms 48380 KB Output is correct
5 Correct 24 ms 28612 KB Output is correct
6 Correct 177 ms 44588 KB Output is correct
7 Correct 107 ms 40980 KB Output is correct
8 Correct 185 ms 44592 KB Output is correct
9 Correct 117 ms 44692 KB Output is correct
10 Correct 106 ms 44268 KB Output is correct
11 Correct 113 ms 45712 KB Output is correct
12 Correct 120 ms 45896 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28492 KB Output is correct
2 Correct 24 ms 28660 KB Output is correct
3 Correct 29 ms 28620 KB Output is correct
4 Correct 28 ms 28656 KB Output is correct
5 Correct 25 ms 28684 KB Output is correct
6 Correct 23 ms 28464 KB Output is correct
7 Correct 22 ms 28560 KB Output is correct
8 Correct 24 ms 28636 KB Output is correct
9 Correct 24 ms 28624 KB Output is correct
10 Correct 175 ms 45068 KB Output is correct
11 Correct 179 ms 47088 KB Output is correct
12 Correct 183 ms 49896 KB Output is correct
13 Correct 187 ms 48380 KB Output is correct
14 Correct 24 ms 28612 KB Output is correct
15 Correct 177 ms 44588 KB Output is correct
16 Correct 107 ms 40980 KB Output is correct
17 Correct 185 ms 44592 KB Output is correct
18 Correct 117 ms 44692 KB Output is correct
19 Correct 106 ms 44268 KB Output is correct
20 Correct 113 ms 45712 KB Output is correct
21 Correct 120 ms 45896 KB Output is correct
22 Correct 156 ms 38340 KB Output is correct
23 Correct 137 ms 37268 KB Output is correct
24 Correct 148 ms 38084 KB Output is correct
25 Correct 27 ms 28620 KB Output is correct
26 Correct 66 ms 32744 KB Output is correct
27 Correct 122 ms 36804 KB Output is correct
28 Correct 100 ms 42740 KB Output is correct
29 Correct 120 ms 45808 KB Output is correct
30 Correct 113 ms 45508 KB Output is correct
31 Correct 24 ms 28620 KB Output is correct