oj.uz

답안 #127398

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127398 2019-07-09T10:24:30 Z Vlatko Deblo (COCI18_deblo) C++14
90 / 90
 175 ms 41336 KB 
#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

# 결과 실행 시간 메모리 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