oj.uz

Submission #173313

# Submission time Handle Problem Language Result Execution time Memory
173313 2020-01-03T18:30:33 Z BigChungus Deblo (COCI18_deblo) C++14
0 / 90
 67 ms 65540 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 = 3e6 + 7, LOG = 3;

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
0 / 90.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 60 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 60 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 60 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)