oj.uz

Submission #116624

# Submission time Handle Problem Language Result Execution time Memory
116624 2019-06-13T08:36:52 Z nandonathaniel Deblo (COCI18_deblo) C++14
90 / 90
 217 ms 41720 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2944 KB Output is correct
5 Correct 5 ms 2944 KB Output is correct
6 Correct 194 ms 41720 KB Output is correct
7 Correct 153 ms 41664 KB Output is correct
8 Correct 172 ms 33432 KB Output is correct
9 Correct 158 ms 33028 KB Output is correct
10 Correct 217 ms 32184 KB Output is correct