oj.uz

Submission #228945

# Submission time Handle Problem Language Result Execution time Memory
228945 2020-05-03T06:50:36 Z VEGAnn Deblo (COCI18_deblo) C++14
0 / 90
 169 ms 31352 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 * kol[0][po][v] * kol[1][po][u];
            ans += 1ll * 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
0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2944 KB Output isn't correct
2 Incorrect 7 ms 2944 KB Output isn't correct
3 Incorrect 6 ms 2944 KB Output isn't correct
4 Incorrect 6 ms 3072 KB Output isn't correct
5 Incorrect 6 ms 3072 KB Output isn't correct
6 Incorrect 80 ms 31288 KB Output isn't correct
7 Incorrect 84 ms 31352 KB Output isn't correct
8 Incorrect 79 ms 24952 KB Output isn't correct
9 Incorrect 84 ms 24204 KB Output isn't correct
10 Incorrect 169 ms 23628 KB Output isn't correct