oj.uz

Submission #228944

# Submission time Handle Problem Language Result Execution time Memory
228944 2020-05-03T06:49:05 Z VEGAnn Deblo (COCI18_deblo) C++14
0 / 90
 103 ms 65144 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][v][po] += kol[bt][po][u];
            kol[1][v][po] += 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 7 ms 2816 KB Output isn't correct
2 Incorrect 6 ms 2816 KB Output isn't correct
3 Runtime error 11 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 11 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 99 ms 65144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 103 ms 63352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 60 ms 14712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 59 ms 14712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 60 ms 16248 KB Execution killed with signal 11 (could be triggered by violating memory limits)