oj.uz

Submission #116623

# Submission time Handle Problem Language Result Execution time Memory
116623 2019-06-13T08:33:53 Z nandonathaniel Deblo (COCI18_deblo) C++14
72 / 90
 243 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN=100005;
const LL LOG=22;

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

void dfs(LL now,LL par){
	for(LL 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(LL i=0;i<LOG;i++){
			ans[i]+=val[nxt][i][0]*val[now][i][1];
			ans[i]+=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(){
    LL n,u,v;
    cin >> n;
    for(LL 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(LL 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(LL i=0;i<LOG;i++){
		ret+=((1<<i)*ans[i]);
	}
	cout << ret << endl;
	return 0;
}

Subtask #1
72.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 5 ms 2816 KB Output is correct
4 Correct 5 ms 3328 KB Output is correct
5 Correct 6 ms 3328 KB Output is correct
6 Runtime error 170 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 172 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Correct 181 ms 62136 KB Output is correct
9 Correct 182 ms 61304 KB Output is correct
10 Correct 243 ms 60664 KB Output is correct