oj.uz

Submission #940526

# Submission time Handle Problem Language Result Execution time Memory
940526 2024-03-07T10:15:30 Z duckindog Deblo (COCI18_deblo) C++17
90 / 90
 80 ms 40752 KB 
#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

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

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5148 KB Output is correct
6 Correct 57 ms 40636 KB Output is correct
7 Correct 50 ms 40752 KB Output is correct
8 Correct 56 ms 32848 KB Output is correct
9 Correct 48 ms 32180 KB Output is correct
10 Correct 80 ms 31324 KB Output is correct