Submission #173316

#	Time	Username	Problem	Language	Result	Execution time	Memory
173316		BigChungus	Deblo (COCI18_deblo)	C++14	90 / 90	181 ms	17144 KiB

deblo

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int N = 1e5 + 7, LOG = 22;

int value[N];
bitset < N > cost;
vector < int > adia[N];
int f[N][2], t[N];

long long cate(0);

void dfs(int nod) {
    f[nod][0] = 0;
    f[nod][1] = 0;
    f[nod][cost[nod]]++;
    cate += cost[nod];
    for (int u : adia[nod]) {
        if (u == t[nod])
            continue;
        t[u] = nod;
        dfs(u);
        cate += 1LL * f[u][0] * f[nod][1] + 1LL * f[u][1] * f[nod][0];
        f[nod][0 ^ cost[nod]] += f[u][0];
        f[nod][1 ^ cost[nod]] += f[u][1];
    }
//    cout << "Nod : " << nod << ' ' << f[nod][0] << ' ' << f[nod][1] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n, u, v;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> value[i];
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        adia[u].push_back(v);
        adia[v].push_back(u);
    }
    int root(1);
    long long ans(0);
    for (int bit = 0; bit < LOG; ++bit) {
        for (int i = 1; i <= n; ++i)
            cost[i] = ((value[i]&(1<<bit)) != 0);
        cate = 0;
        dfs(root);
        ans += cate * (1<<bit);
    }
    cout << ans;
    return 0;
}

• Subtask 1: 90 / 90