oj.uz

답안 #299507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299507 2020-09-15T05:14:19 Z shivensinha4 Putovanje (COCI20_putovanje) C++17
110 / 110
 211 ms 28664 KB 
/*
COCI 2020 Putovanje
- Essentially want to find the number of times we traverse each edge
- We use the fact that A->B = A->LCA(A, B)->B
    - A path A->B where B is an ancestor of A passes through the "parent"
      edge of C iff B is an ancestor of C and C is an ancestor of A
    - This means we can mark A with 1 and B with -1
    - So the subtree sum is the number of paths passing through an edge!
- DFS to get DFS order and use a Fenwick tree to do stuff
- Complexity: O(N log N)
*/

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n;
vector<int> graph[200001];
ll bit[200001];
int tin[200001], tout[200001], timer = 0;
int anc[200001][20];

void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    FOR(i, 1, 20) anc[node][i] = anc[anc[node][i - 1]][i - 1];

    tin[node] = ++timer;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}

bool is_ancestor(int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; }

int lca(int a, int b) {
    if (is_ancestor(a, b)) return a;
    for (int i = 19; ~i; i--) {
        if (anc[a][i] && !is_ancestor(anc[a][i], b)) a = anc[a][i];
    }
    return anc[a][0];
}

void update(int pos, ll val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }

ll query(int a, int b) {
    ll ans = 0;
    for (; b; b -= (b & (-b))) ans += bit[b];
    for (a--; a; a -= (a & -a)) ans -= bit[a];
    return ans;
}

vector<int> edges[200001];

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    FOR(i, 1, n) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        graph[a].push_back(b);
        graph[b].push_back(a);
        edges[i] = {a, b, c, d};
    }
    dfs();

    FOR(i, 1, n) {
        int l = lca(i, i + 1);
        update(tin[i], 1);
        update(tin[i + 1], 1);
        update(tin[l], -2);
    }

    ll ans = 0;
    FOR(i, 1, n) {
        int x;
        if (is_ancestor(edges[i][0], edges[i][1])) x = edges[i][1];
        else x = edges[i][0];

        ans += min((ll)edges[i][3], (ll)edges[i][2] * query(tin[x], tout[x]));
    }
    cout << ans;
    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 10 ms 10112 KB Output is correct
4 Correct 9 ms 10112 KB Output is correct
5 Correct 9 ms 10112 KB Output is correct
6 Correct 7 ms 9728 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9984 KB Output is correct
9 Correct 9 ms 9984 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 26104 KB Output is correct
2 Correct 203 ms 26872 KB Output is correct
3 Correct 200 ms 28536 KB Output is correct
4 Correct 211 ms 28664 KB Output is correct
5 Correct 7 ms 9856 KB Output is correct
6 Correct 155 ms 25720 KB Output is correct
7 Correct 105 ms 21368 KB Output is correct
8 Correct 164 ms 26104 KB Output is correct
9 Correct 94 ms 27000 KB Output is correct
10 Correct 90 ms 26360 KB Output is correct
11 Correct 98 ms 27768 KB Output is correct
12 Correct 111 ms 27768 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 8 ms 9984 KB Output is correct
3 Correct 10 ms 10112 KB Output is correct
4 Correct 9 ms 10112 KB Output is correct
5 Correct 9 ms 10112 KB Output is correct
6 Correct 7 ms 9728 KB Output is correct
7 Correct 8 ms 9856 KB Output is correct
8 Correct 8 ms 9984 KB Output is correct
9 Correct 9 ms 9984 KB Output is correct
10 Correct 159 ms 26104 KB Output is correct
11 Correct 203 ms 26872 KB Output is correct
12 Correct 200 ms 28536 KB Output is correct
13 Correct 211 ms 28664 KB Output is correct
14 Correct 7 ms 9856 KB Output is correct
15 Correct 155 ms 25720 KB Output is correct
16 Correct 105 ms 21368 KB Output is correct
17 Correct 164 ms 26104 KB Output is correct
18 Correct 94 ms 27000 KB Output is correct
19 Correct 90 ms 26360 KB Output is correct
20 Correct 98 ms 27768 KB Output is correct
21 Correct 111 ms 27768 KB Output is correct
22 Correct 149 ms 24984 KB Output is correct
23 Correct 123 ms 23212 KB Output is correct
24 Correct 138 ms 24696 KB Output is correct
25 Correct 8 ms 9856 KB Output is correct
26 Correct 58 ms 16760 KB Output is correct
27 Correct 116 ms 22520 KB Output is correct
28 Correct 82 ms 25080 KB Output is correct
29 Correct 101 ms 27768 KB Output is correct
30 Correct 98 ms 27640 KB Output is correct
31 Correct 8 ms 9984 KB Output is correct