제출 #442038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442038		Abrar_Al_Samit	Putovanje (COCI20_putovanje)	C++17	110 / 110	187 ms	49896 KiB

putovanje

#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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65