oj.uz

Submission #940529

# Submission time Handle Problem Language Result Execution time Memory
940529 2024-03-07T10:16:23 Z duckindog Deblo (COCI18_deblo) C++17
90 / 90
 76 ms 40740 KB 
#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

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.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 5212 KB Output is correct
6 Correct 49 ms 40696 KB Output is correct
7 Correct 52 ms 40740 KB Output is correct
8 Correct 54 ms 32848 KB Output is correct
9 Correct 66 ms 32264 KB Output is correct
10 Correct 76 ms 31472 KB Output is correct