Submission #855906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855906	2023-10-02T08:52:34 Z	wakandaaa	Deblo (COCI18_deblo)	C++17	90 / 90	166 ms	14428 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	5724 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	5780 KB	Output is correct
5	Correct	2 ms	5724 KB	Output is correct
6	Correct	154 ms	14420 KB	Output is correct
7	Correct	154 ms	14428 KB	Output is correct
8	Correct	166 ms	11972 KB	Output is correct
9	Correct	162 ms	11844 KB	Output is correct
10	Correct	151 ms	11348 KB	Output is correct