Submission #522427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522427	2022-02-05T02:07:28 Z	KoD	Deblo (COCI18_deblo)	C++17	90 / 90	144 ms	12616 KB

deblo

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::tuple;
using std::pair;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }    
    vector<vector<int>> graph(N);
    for (int i = 1; i < N; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1, b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    vector<int> parent(N), order;
    order.reserve(N);
    auto dfs = [&](auto&& self, const int u) -> void {
        order.push_back(u);
        for (const int v : graph[u]) {
            if (v != parent[u]) {
                parent[v] = u;
                self(self, v);
            }
        }
    };
    parent[0] = -1;
    dfs(dfs, 0);
    vector<int> accum = A;
    for (int i = 1; i < N; ++i) {
        accum[order[i]] ^= accum[parent[order[i]]];
    }
    long long ans = std::accumulate(A.begin(), A.end(), 0ll);
    for (int d = 0; d < 22; ++d) {
        long long cnt = 0;
        vector<array<int, 2>> count(N);
        for (int i = N - 1; i >= 0; --i) {
            const int u = order[i];
            const int a = A[u] >> d & 1, ac = accum[u] >> d & 1;
            for (const int v : graph[u]) {
                if (v != parent[u]) {
                    cnt += count[v][(a ^ ac ^ 1)];
                    for (int k = 0; k < 2; ++k) {
                        cnt += (long long)count[v][k] * count[u][a ^ k ^ 1];
                    }
                    for (int k = 0; k < 2; ++k) {
                        count[u][k] += count[v][k];
                    }
                }
            }
            count[u][ac] += 1;
        }
        ans += cnt << d;
    }
    std::cout << ans << '\n';
    return 0;
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	316 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	56 ms	12616 KB	Output is correct
7	Correct	54 ms	12484 KB	Output is correct
8	Correct	93 ms	10532 KB	Output is correct
9	Correct	87 ms	10268 KB	Output is correct
10	Correct	144 ms	10024 KB	Output is correct