Submission #940529

#	Time	Username	Problem	Language	Result	Execution time	Memory
940529		duckindog	Deblo (COCI18_deblo)	C++17	90 / 90	76 ms	40740 KiB

deblo

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100'000 + 10;
int n;
int a[N];
vector<int> ad[N];
 
long long answer;
int d[N][32][2];
void dfs(int u, int p = 0) { 
  for (int i = 1; i <= 31; ++i) d[u][i][a[u] >> i - 1 & 1] += 1;
  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    dfs(v, u);
    for (int i = 1; i <= 31; ++i) { 
      for (int b = 0; b < 2; ++b) answer += 1ll * d[v][i][b] * d[u][i][1 - b] * (1 << i - 1);
      for (int b = 0; b < 2; ++b) {
        int bit = (a[u] >> i - 1 & 1);
        d[u][i][bit ^ b] += d[v][i][b];
      }
    }
  }
}
 
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 2; i <= n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) answer += a[i];
  cout << answer << "\n";
}

Compilation message (stderr)

deblo.cpp: In function 'void dfs(int, int)':
deblo.cpp:14:51: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   14 |   for (int i = 1; i <= 31; ++i) d[u][i][a[u] >> i - 1 & 1] += 1;
      |                                                 ~~^~~
deblo.cpp:19:89: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   19 |       for (int b = 0; b < 2; ++b) answer += 1ll * d[v][i][b] * d[u][i][1 - b] * (1 << i - 1);
      |                                                                                       ~~^~~
deblo.cpp:21:30: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   21 |         int bit = (a[u] >> i - 1 & 1);
      |                            ~~^~~

• Subtask 1: 90 / 90