Submission #873910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873910	2023-11-16T02:41:29 Z	noiaint	Deblo (COCI18_deblo)	C++17	90 / 90	167 ms	14476 KB

deblo

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file ""
using namespace std;
 
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1
 
template<class X, class Y> bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
template<class X, class Y> bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}
 
int n, k;
vector<int> adj[N];
int val[N];
 
long long ans = 0;
 
struct centroid {
    int vis[N], par[N], sz[N];
 
    // map<int, int> d;
    // int d[N];
    int cnt[2][lg + 1];
    centroid() {
    }
 
    void getsize(int u, int p = -1) {
        sz[u] = 1;
        for (int v : adj[u]) {
            if (v == p || vis[v]) continue;
            getsize(v, u);
            sz[u] += sz[v];
        }
    }
 
    int findcentroid(int u, int n, int p = -1) {
        if (sz[u] <= n / 2)
            return p;
        pair<int, int> big = {0, 0};
        for (int v : adj[u]) {
            if (v == p || vis[v]) continue;
            big = max(big, {sz[v], v});
        }
        return findcentroid(big.se, n, u);
    }
 
    void dfs(int u, int p, int h, int op) {
        h ^= val[u];
        for (int i = 0; i <= lg; ++i) {
            if (op == 0) {
                ans += bit(i) * cnt[getbit(h, i) ^ 1][i];
            }
            else {
                cnt[getbit(h, i)][i]++;
            }
        }
 
        for (int v : adj[u]) if (v != p && !vis[v]) {
            dfs(v, u, h, op);
        }
    }
 
    void decompose(int u) {
        getsize(u);
        u = findcentroid(u, sz[u]);
        vis[u] = true;
        
        memset(cnt, 0, sizeof cnt);
        for (int i = 0; i <= lg; ++i)
            cnt[getbit(val[u], i)][i]++;
 
        ans += val[u];
 
        for (int v : adj[u]) if (!vis[v]) {
            dfs(v, u, 0, 0);
            dfs(v, u, val[u], 1);
        }
 
        for (int v : adj[u]) if (!vis[v]) {
            decompose(v);
        }
    }
 
} cen;
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    // freopen(file".inp", "r",stdin);
    // freopen(file".out", "w",stdout);
 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    cen.decompose(1);
    cout << ans;
 
    return 0;
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5720 KB	Output is correct
2	Correct	2 ms	5724 KB	Output is correct
3	Correct	1 ms	5724 KB	Output is correct
4	Correct	2 ms	5724 KB	Output is correct
5	Correct	2 ms	5788 KB	Output is correct
6	Correct	154 ms	14476 KB	Output is correct
7	Correct	153 ms	14416 KB	Output is correct
8	Correct	167 ms	11856 KB	Output is correct
9	Correct	162 ms	11600 KB	Output is correct
10	Correct	145 ms	11456 KB	Output is correct