oj.uz

Submission #300796

# Submission time Handle Problem Language Result Execution time Memory
300796 2020-09-17T13:38:16 Z zecookiez Deblo (COCI18_deblo) C++17
90 / 90
 205 ms 48760 KB 
#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int len(const C&c){return int(c.size());}

const int MAXN = 100005;
const int BIT = 22;

vector<int> adj[MAXN];
int arr[MAXN];
long long ans, dp[2][BIT][MAXN];

void helper(int node, int prev = -1){
    for(int i = 0; i < BIT; ++i) dp[(arr[node] >> i) & 1][i][node] = 1;
    long long C, D;
    for(int nxt : adj[node]){
        if(nxt == prev) continue;
        helper(nxt, node);
        for(int j, i = 0; i < BIT; ++i){
            C = dp[1][i][nxt];  D = dp[0][i][nxt];
            ans += ((dp[1][i][node] * D + dp[0][i][node] * C) << i);
            j = (arr[node] >> i) & 1;
            dp[j][i][node] += D;
            dp[j ^ 1][i][node] += C;
        }
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    for(int i = 1; i <= N; ++i) cin >> arr[i], ans += arr[i];
    for(int a, b, i = 1; i < N; ++i){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    helper(1); cout << ans << '\n';
    return 0;
}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2944 KB Output is correct
2 Correct 3 ms 2944 KB Output is correct
3 Correct 2 ms 2944 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 92 ms 48760 KB Output is correct
7 Correct 95 ms 48760 KB Output is correct
8 Correct 99 ms 43768 KB Output is correct
9 Correct 92 ms 43256 KB Output is correct
10 Correct 205 ms 42720 KB Output is correct