oj.uz

Submission #487669

# Submission time Handle Problem Language Result Execution time Memory
487669 2021-11-16T10:58:50 Z KazamaHoang Putovanje (COCI20_putovanje) C++14
110 / 110
 136 ms 24212 KB 
#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];
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 3 ms 4940 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 3 ms 5196 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 20968 KB Output is correct
2 Correct 120 ms 22212 KB Output is correct
3 Correct 135 ms 24212 KB Output is correct
4 Correct 136 ms 23744 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 106 ms 20600 KB Output is correct
7 Correct 60 ms 16572 KB Output is correct
8 Correct 116 ms 20804 KB Output is correct
9 Correct 69 ms 21428 KB Output is correct
10 Correct 67 ms 20876 KB Output is correct
11 Correct 65 ms 22236 KB Output is correct
12 Correct 68 ms 22168 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5196 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 3 ms 5196 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 5068 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 116 ms 20968 KB Output is correct
11 Correct 120 ms 22212 KB Output is correct
12 Correct 135 ms 24212 KB Output is correct
13 Correct 136 ms 23744 KB Output is correct
14 Correct 3 ms 5068 KB Output is correct
15 Correct 106 ms 20600 KB Output is correct
16 Correct 60 ms 16572 KB Output is correct
17 Correct 116 ms 20804 KB Output is correct
18 Correct 69 ms 21428 KB Output is correct
19 Correct 67 ms 20876 KB Output is correct
20 Correct 65 ms 22236 KB Output is correct
21 Correct 68 ms 22168 KB Output is correct
22 Correct 121 ms 17804 KB Output is correct
23 Correct 106 ms 16332 KB Output is correct
24 Correct 116 ms 17744 KB Output is correct
25 Correct 3 ms 5068 KB Output is correct
26 Correct 40 ms 10952 KB Output is correct
27 Correct 86 ms 15788 KB Output is correct
28 Correct 55 ms 19552 KB Output is correct
29 Correct 67 ms 22216 KB Output is correct
30 Correct 67 ms 22276 KB Output is correct
31 Correct 3 ms 5196 KB Output is correct