Submission #300796

#	Time	Username	Problem	Language	Result	Execution time	Memory
300796		zecookiez	Deblo (COCI18_deblo)	C++17	90 / 90	205 ms	48760 KiB

deblo

#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 / 90