Submission #116624

#	Time	Username	Problem	Language	Result	Execution time	Memory
116624		nandonathaniel	Deblo (COCI18_deblo)	C++14	90 / 90	217 ms	41720 KiB

deblo

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=100005;
const LL LOG=22;

int bit[MAXN][LOG],val[MAXN][LOG][2],a[MAXN];
LL ans[LOG];
vector<int> adj[MAXN];

void dfs(LL now,LL par){
	for(int i=0;i<LOG;i++){
		val[now][i][bit[now][i]]++;
		ans[i]+=bit[now][i];
	}
	for(auto nxt : adj[now]){
		if(nxt==par)continue;
		dfs(nxt,now);
		for(int i=0;i<LOG;i++){
			ans[i]+=(LL)val[nxt][i][0]*val[now][i][1];
			ans[i]+=(LL)val[nxt][i][1]*val[now][i][0];
			val[now][i][0]+=val[nxt][i][bit[now][i]];
			val[now][i][1]+=val[nxt][i][!bit[now][i]];
		}
	}
}

int main(){
    int n,u,v;
    cin >> n;
    for(int i=1;i<=n;i++){
    	cin >> a[i];
    	for(int j=0;j<LOG;j++){
    		if(a[i] & (1<<j))bit[i][j]=1;
		}
	}
    for(int i=1;i<n;i++){
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
	}
	dfs(1,-1);
	LL ret=0;
	for(int i=0;i<LOG;i++){
		ret+=((1<<i)*ans[i]);
	}
	cout << ret << endl;
	return 0;
}

• Subtask 1: 90 / 90