제출 #487668

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

putovanje

#include <bits/stdc++.h>

using namespace std;

string to_string(const string& s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) { 
    return (b ? "true" : "false");
}
 
string to_string(char ch) {
    return string(1, ch);
}
 
string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); ++ i) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    reverse(res.begin(), res.end());
    return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto& x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
template <typename A> 
void debug_array(A a[], int n) {
    string res = "{";
    for (int i = 1; i <= n; ++ i) {
        if (i != 1) {
            res += ", ";
        }
        res += to_string(a[i]);
    }
    res += '}';
    cerr << res << endl;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42 
#endif

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];
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) {
    for (int& id : adj[u])
        if (id != prevEdge) {
            int v = edges[id].get_other(u);
            DFS(v, id);
            add[u] += add[v];
        }
    res += min((long long)add[u] * edges[prevEdge].cost_one, (long long)edges[prevEdge].cost_two);
}

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);
    add[c] -= 2;
    ++ add[u];
    ++ add[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);
    cout << res;
    return 0;
}

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