제출 #487645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487645		KazamaHoang	Putovanje (COCI20_putovanje)	C++14	25 / 110	199 ms	26944 KiB

putovanje

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int u, v, cost_one, cost_two;

    int get_other(int x) const {
        return u ^ v ^ x;
    }
};

int n;
vector<int> adj[200005];
Edge edges[200005];
int par[200005][20], h[200005], add[200005], sub[200005];
long long res = 0;

void dfs(int u, int prevEdge) {
    for (int& id : adj[u]) 
        if (prevEdge != id) {
            int v = edges[id].get_other(u);
            h[v] = h[u] + 1;
            par[v][0] = u;
            for (int i = 1; (1 << i) <= n; ++ i)
                par[v][i] = par[par[v][i-1]][i-1];
            dfs(v, id);
        }
}

void DFS(int u, int prevEdge, int curAdd) {
    curAdd += add[u];
    res += min((long long)curAdd * edges[prevEdge].cost_one, (long long)edges[prevEdge].cost_two);
    curAdd += sub[u];
    for (int& id : adj[u])
        if (id != prevEdge) {
            int v = edges[id].get_other(u);
            DFS(v, id, curAdd);
        }
}

int get_lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    int delta = h[u] - h[v], i;
    for (i = 0; (1 << i) <= n; ++ i)
        if (delta >> i & 1) 
            u = par[u][i];
    if (u == v) return u;
    for (-- i; i >= 0; -- i) 
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    return par[u][0];
}

int jump(int u, int x) {
    for (int i = 0; (1 << i) <= n; ++ i)
        if (x >> i & 1)
            u = par[u][i];
    return u;
}

void update(int u, int v) {
    int c = get_lca(u, v);
    int par_u = jump(u, h[u] - h[c] - 1);
    int par_v = jump(v, h[v] - h[c] - 1);
    if (u == c) {
        ++ add[par_v];
        -- sub[v];
    } else if (v == c) {
        ++ add[par_u];
        -- sub[u];
    } else {
        ++ add[par_u];
        ++ add[par_v];
        -- sub[u];
        -- sub[v];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; ++ i) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edges[i] = {u, v, c, d};
        adj[u].push_back(i);
        adj[v].push_back(i);        
    }
    dfs(1, 0);
    for (int i = 1; i < n; ++ i) 
        update(i, i + 1);
    DFS(1, 0, 0);
    cout << res;
    return 0;
}

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