oj.uz

Submission #173316

# Submission time Handle Problem Language Result Execution time Memory
173316 2020-01-03T18:32:30 Z BigChungus Deblo (COCI18_deblo) C++14
90 / 90
 181 ms 17144 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 123 ms 17144 KB Output is correct
7 Correct 125 ms 17016 KB Output is correct
8 Correct 123 ms 10792 KB Output is correct
9 Correct 125 ms 10104 KB Output is correct
10 Correct 181 ms 9356 KB Output is correct