Submission #200086

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200086	2020-02-05T10:15:26 Z	Saboon	Deblo (COCI18_deblo)	C++14	90 / 90	348 ms	18296 KB

deblo

#include <bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10;
int l[maxn], r[maxn], u[maxn], d[maxn];

vector <int> v[maxn];
int a[maxn];

int ted[maxn][2];

ll ans;

void dfs (int u, int bit, int par = -1) {
	bool p = (a[u] >> bit) & 1;
	ted[u][p] = 0;
	ted[u][1 - p] = 0;
	for (auto w : v[u]) {
		if (w != par) {
			dfs (w, bit, u);
			ted[u][0] += ted[w][0];
			ted[u][1] += ted[w][1];
		}
	}
	
	if (p) {
		ll tmp = 0;
		for (auto w : v[u]) {
			if (w != par) {
				tmp += (1ll << bit) * ted[w][0] * (ted[u][0] - ted[w][0]);
				tmp += (1ll << bit) * ted[w][1] * (ted[u][1] - ted[w][1]);
			}
		}
		ans += tmp / 2;
		ans += (ted[u][0] + 1) * (1ll << bit);
		tmp = ted[u][0];
		ted[u][0] = ted[u][1];
		ted[u][1] = tmp + 1;
	}
	else {
		ll tmp = 0;
		for (auto w : v[u]) {
			if (w != par) {
				tmp += (1ll << bit) * ted[w][0] * (ted[u][1] - ted[w][1]);
				tmp += (1ll << bit) * ted[w][1] * (ted[u][0] - ted[w][0]);
			}
		}
		ans += tmp / 2;
		ans += ted[u][1] * (1ll << bit);
		ted[u][0] ++;
	}
}

int main(){ 
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n - 1; i++) {
		int u, w;
		cin >> u >> w;
		v[u].PB (w);
		v[w].PB (u);
	}
	for (int i = 0; i < 23; i++) {
		dfs (1, i);
	}
	cout << ans << endl;
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2680 KB	Output is correct
2	Correct	7 ms	2680 KB	Output is correct
3	Correct	6 ms	2680 KB	Output is correct
4	Correct	7 ms	2808 KB	Output is correct
5	Correct	7 ms	2808 KB	Output is correct
6	Correct	169 ms	18296 KB	Output is correct
7	Correct	164 ms	18168 KB	Output is correct
8	Correct	146 ms	10620 KB	Output is correct
9	Correct	165 ms	9976 KB	Output is correct
10	Correct	348 ms	8952 KB	Output is correct