Submission #127398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
127398	2019-07-09T10:24:30 Z	Vlatko	Deblo (COCI18_deblo)	C++14	90 / 90	175 ms	41336 KB

deblo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;


const int maxn = 100010;
const int maxval = 3000000;
const int maxlog = 22;

int n;
vector<int> adj[maxn];
ll numpaths[maxlog];
int val[maxn][maxlog]; // whether i-th bit is on
int dp[maxn][maxlog][2];

void dfs(int u, int p) {
	for (int i = 0; i < maxlog; ++i) {
		dp[u][i][val[u][i]] += 1;
		numpaths[i] += val[u][i];
	}
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		for (int i = 0; i < maxlog; ++i) {
			numpaths[i] += 1LL * dp[u][i][0] * dp[v][i][1];
			numpaths[i] += 1LL * dp[u][i][1] * dp[v][i][0];
			dp[u][i][0] += dp[v][i][0^val[u][i]];
			dp[u][i][1] += dp[v][i][1^val[u][i]];
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int u = 1; u <= n; ++u) {
		int x;
		cin >> x;
		for (int i = 0; i < maxlog; ++i) {
			val[u][i] = (x & (1 << i)) >> i;
		}
	}
	for (int i = 0; i < n-1; ++i) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	memset(dp, 0, sizeof(dp));
	dfs(1, -1);
	ll ans = 0;
	for (int b = 0; b < maxlog; ++b) {
		ans += numpaths[b] * (1 << b);
	}
	cout << ans << '\n';
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	19960 KB	Output is correct
2	Correct	18 ms	19960 KB	Output is correct
3	Correct	19 ms	19960 KB	Output is correct
4	Correct	19 ms	20088 KB	Output is correct
5	Correct	19 ms	20088 KB	Output is correct
6	Correct	109 ms	41336 KB	Output is correct
7	Correct	98 ms	41336 KB	Output is correct
8	Correct	107 ms	35004 KB	Output is correct
9	Correct	104 ms	34268 KB	Output is correct
10	Correct	175 ms	33656 KB	Output is correct