oj.uz

Submission #487668

# Submission time Handle Problem Language Result Execution time Memory
487668 2021-11-16T10:58:13 Z KazamaHoang Putovanje (COCI20_putovanje) C++14
110 / 110
 135 ms 24684 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5328 KB Output is correct
4 Correct 4 ms 5292 KB Output is correct
5 Correct 4 ms 5348 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 21024 KB Output is correct
2 Correct 129 ms 22352 KB Output is correct
3 Correct 132 ms 24144 KB Output is correct
4 Correct 135 ms 23748 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 106 ms 20728 KB Output is correct
7 Correct 61 ms 16636 KB Output is correct
8 Correct 112 ms 20912 KB Output is correct
9 Correct 61 ms 21340 KB Output is correct
10 Correct 59 ms 20884 KB Output is correct
11 Correct 64 ms 22224 KB Output is correct
12 Correct 72 ms 22212 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5328 KB Output is correct
4 Correct 4 ms 5292 KB Output is correct
5 Correct 4 ms 5348 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 3 ms 5200 KB Output is correct
10 Correct 114 ms 21024 KB Output is correct
11 Correct 129 ms 22352 KB Output is correct
12 Correct 132 ms 24144 KB Output is correct
13 Correct 135 ms 23748 KB Output is correct
14 Correct 3 ms 5068 KB Output is correct
15 Correct 106 ms 20728 KB Output is correct
16 Correct 61 ms 16636 KB Output is correct
17 Correct 112 ms 20912 KB Output is correct
18 Correct 61 ms 21340 KB Output is correct
19 Correct 59 ms 20884 KB Output is correct
20 Correct 64 ms 22224 KB Output is correct
21 Correct 72 ms 22212 KB Output is correct
22 Correct 112 ms 20004 KB Output is correct
23 Correct 96 ms 18156 KB Output is correct
24 Correct 107 ms 19700 KB Output is correct
25 Correct 4 ms 5200 KB Output is correct
26 Correct 35 ms 11672 KB Output is correct
27 Correct 87 ms 17736 KB Output is correct
28 Correct 55 ms 21144 KB Output is correct
29 Correct 70 ms 24684 KB Output is correct
30 Correct 67 ms 24292 KB Output is correct
31 Correct 3 ms 5200 KB Output is correct