Submission #940498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
940498	2024-03-07T09:59:32 Z	duckindog	Deblo (COCI18_deblo)	C++17	90 / 90	185 ms	15416 KB

deblo

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n;
int a[N];
vector<int> ad[N];

int tsz;
int sz[N];
bool mk[N];
void dfs1(int u, int p = 0) { 
  sz[u] = 1;
  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
  tsz = sz[u];
}
int dfs2(int u, int p = 0) { 
  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    if (sz[v] > tsz / 2) return dfs2(v, u);
  }  
  return u;
}

vector<int> lst;
int d[32][2];
void dfs3(int u, int p, int sw) { 
  lst.push_back(sw);
  for (const auto& v : ad[u]) if (v != p && !mk[v]) dfs3(v, u, sw ^ a[v]);
}

long long answer;
void dfs4(int u, int p = 0) { 
  dfs1(u, p);
  mk[u = dfs2(u, p)] = true;
  
  for (int i = 1; i <= 31; ++i) d[i][0] = d[i][1] = 0;

  for (const auto& v : ad[u]) { 
    if (v == p || mk[v]) continue;
    lst.clear(); dfs3(v, u, a[v]);
    
    for (const auto& w : lst) { 
      for (int i = 1; i <= 31; ++i) { 
        int bit = ((w ^ a[u]) >> i - 1 & 1);
        answer += 1ll * d[i][1 - bit] * (1 << i - 1);
      }
    }
    
    for (const auto& w : lst) { 
      for (int i = 1; i <= 31; ++i) d[i][w >> i - 1 & 1] += 1;
    } 

  }
  for (int i = 1; i <= 31; ++i) {
    int bit = (a[u] >> i - 1 & 1);
    answer += 1ll * d[i][1 - bit] * (1 << i - 1);
  }
  
  for (const auto& v : ad[u]) if (v != p && !mk[v]) dfs4(v, u);
}

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);
  }

  for (int i = 1; i <= n; ++i) answer += a[i];
  dfs4(1); 
  cout << answer << "\n";
}

Compilation message

deblo.cpp: In function 'void dfs4(int, int)':
deblo.cpp:50:36: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   50 |         int bit = ((w ^ a[u]) >> i - 1 & 1);
      |                                  ~~^~~
deblo.cpp:51:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |         answer += 1ll * d[i][1 - bit] * (1 << i - 1);
      |                                               ~~^~~
deblo.cpp:56:49: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   56 |       for (int i = 1; i <= 31; ++i) d[i][w >> i - 1 & 1] += 1;
      |                                               ~~^~~
deblo.cpp:61:26: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   61 |     int bit = (a[u] >> i - 1 & 1);
      |                        ~~^~~
deblo.cpp:62:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |     answer += 1ll * d[i][1 - bit] * (1 << i - 1);
      |                                           ~~^~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2988 KB	Output is correct
2	Correct	1 ms	2908 KB	Output is correct
3	Correct	1 ms	3120 KB	Output is correct
4	Correct	3 ms	3164 KB	Output is correct
5	Correct	2 ms	3188 KB	Output is correct
6	Correct	185 ms	15416 KB	Output is correct
7	Correct	169 ms	15204 KB	Output is correct
8	Correct	153 ms	10064 KB	Output is correct
9	Correct	153 ms	9596 KB	Output is correct
10	Correct	138 ms	8904 KB	Output is correct