oj.uz

Submission #228946

# Submission time Handle Problem Language Result Execution time Memory
228946 2020-05-03T06:53:55 Z VEGAnn Deblo (COCI18_deblo) C++14
90 / 90
 191 ms 31224 KB 
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 100100;
const int PW = 22;
ll ans = 0;
vector<int> g[N];
int n, vl[N], kol[2][PW][N];

void dfs(int v, int p){
    ans += vl[v];

    for (int po = 0; po < PW; po++)
        kol[bool(vl[v] & (1 << po))][po][v]++;

    for (int u : g[v]){
        if (u == p) continue;
        dfs(u, v);

        for (int po = 0; po < PW; po++){
            ans += (1ll << po) * kol[0][po][v] * kol[1][po][u];
            ans += (1ll << po) * kol[1][po][v] * kol[0][po][u];

            int bt = bool(vl[v] & (1 << po));

            kol[0][po][v] += kol[bt][po][u];
            kol[1][po][v] += kol[bt ^ 1][po][u];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> vl[i];

    for (int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].PB(y);
        g[y].PB(x);
    }

    dfs(0, -1);

    cout << ans;

    return 0;
}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2944 KB Output is correct
2 Correct 6 ms 2944 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 7 ms 3200 KB Output is correct
5 Correct 7 ms 3200 KB Output is correct
6 Correct 80 ms 31224 KB Output is correct
7 Correct 83 ms 31224 KB Output is correct
8 Correct 88 ms 24824 KB Output is correct
9 Correct 85 ms 24184 KB Output is correct
10 Correct 191 ms 23628 KB Output is correct