Submission #1228506

#TimeUsernameProblemLanguageResultExecution timeMemory
1228506CodeLakVNDeblo (COCI18_deblo)C++20
90 / 90
133 ms13032 KiB
#include <bits/stdc++.h> using namespace std; #define task "main" #define no "NO" #define yes "YES" #define F first #define S second #define vec vector #define _mp make_pair #define ii pair<int, int> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define evoid(val) return void(std::cout << val) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) const int MAX_N = (int)1e5 + 5; int numNode; vector<int> adj[MAX_N]; int val[MAX_N]; int child[MAX_N]; bool del[MAX_N]; long long ans = 0; int countChild(int u, int p) { child[u] = 1; for (int v : adj[u]) { if (v == p || del[v]) continue; child[u] += countChild(v, u); } return child[u]; } int centroid(int u, int p, int m) { for (int v : adj[u]) { if (del[v] || v == p) continue; if (child[v] > m / 2) return centroid(v, u, m); } return u; } int cnt[23][2]; void dfs(int u, int p, int XOR, bool ok) { if (ok) { ans += XOR; FOR(i, 0, 22) cnt[i][(XOR >> i) & 1]++; } else { FOR(i, 0, 22) ans += (1LL << i) * cnt[i][((XOR >> i) & 1) ^ 1]; } for (int v : adj[u]) { if (del[v] || v == p) continue; dfs(v, u, XOR ^ val[v], ok); } } void decompose(int u) { int m = countChild(u, -1); u = centroid(u, -1, m); del[u] = 1; ans += val[u]; for (int v : adj[u]) if (!del[v]) { dfs(v, u, val[v], 0); dfs(v, u, val[u] ^ val[v], 1); } FOR(i, 0, 22) cnt[i][0] = cnt[i][1] = 0; for (int v : adj[u]) if (!del[v]) decompose(v); } void solve() { cin >> numNode; FOR(i, 1, numNode) cin >> val[i]; FOR(i, 1, numNode - 1) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } memset(cnt, 0, sizeof(cnt)); ans = 0; decompose(1); cout << ans << "\n"; } int32_t main() { if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); bool multitest = 0; int numTest = 1; if (multitest) cin >> numTest; while (numTest--) { solve(); } return 0; } /* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

deblo.cpp: In function 'int32_t main()':
deblo.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
deblo.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...