Submission #650545

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
650545	2022-10-14T08:09:15 Z	Koful123	Deblo (COCI18_deblo)	C++17	90 / 90	514 ms	24900 KB

deblo

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 1e5 + 5;
vector<int> adj[N],odd(N),even(N),bit(N,0),val(N);

void dfs(int node,int par,int k){
	vector<int> a;
	for(int go : adj[node]){
		if(go != par) dfs(go,node,k);
	}
	int p = (1ll<<k) & val[node],o = 0,e = 0;
	for(int go : adj[node]){
		if(go == par) continue;
		if(p) odd[node] += even[go],even[node] += odd[go];
		else odd[node] += odd[go],even[node] += even[go];
		a.pb(go),o += odd[go],e += even[go];
	}
	if(p){
		int cur = 0;
		for(int x : a){
			cur += (o - odd[x]) * odd[x];
			cur += (e - even[x]) * even[x];
		}	
		bit[k] += cur / 2;
	}
	else{
		int cur = 0;
		for(int x : a){
			cur += even[x] * (o - odd[x]); 
			cur += odd[x] * (e - even[x]);
		}
		bit[k] += cur / 2;
	}
	bit[k] += (odd[node] += !!p);
	even[node] += !p;
}

void solve(){	

	int n; cin >> n;
	for(int i=1;i<=n;i++){
		cin >> val[i];
	}

	for(int i=1;i<n;i++){
		int a,b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}

	for(int i=0;i<30;i++){
		odd.assign(N,0),even.assign(N,0);
		dfs(1,0,i);
	}

	int ans = 0;
	for(int i=0;i<30;i++){
		ans += (1ll<<i) * bit[i];
	}

	cout << ans << endl;
}	

signed main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--)
		solve();

	return 0;
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	5716 KB	Output is correct
2	Correct	6 ms	5716 KB	Output is correct
3	Correct	6 ms	5828 KB	Output is correct
4	Correct	9 ms	5920 KB	Output is correct
5	Correct	8 ms	5844 KB	Output is correct
6	Correct	217 ms	24900 KB	Output is correct
7	Correct	216 ms	24848 KB	Output is correct
8	Correct	210 ms	13864 KB	Output is correct
9	Correct	254 ms	12620 KB	Output is correct
10	Correct	514 ms	11308 KB	Output is correct