oj.uz

Submission #228962

# Submission time Handle Problem Language Result Execution time Memory
228962 2020-05-03T07:35:16 Z kartel Deblo (COCI18_deblo) C++14
0 / 90
 124 ms 65536 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

int n, i, x, y, a[N];
ll ans;
int f[N][25][2];
vector <int> g[N];

void dfs(int v, int pr)
{
    for (int bt = 0; bt <= 23; bt++)
        f[v][bt][(a[v] & (1 << bt))]++;

    for (auto u : g[v])
    {
        if (u == pr) continue;

        dfs(u, v);

        for (int bt = 0; bt <= 23; bt++)
        {
            ans += (1ll << bt) * f[v][bt][0] * f[u][bt][1];
            ans += (1ll << bt) * f[v][bt][1] * f[u][bt][0];

            int nbt = ((1 << bt) & a[v]);

            f[v][bt][0] += f[u][bt][nbt];
            f[v][bt][1] += f[u][bt][1 - nbt];
        }
    }
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i], ans += a[i];

    for (i = 1; i < n; i++)
    {
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    dfs(1, -1);

    cout << ans << el;
}

Subtask #1
0 / 90.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2688 KB Output isn't correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Runtime error 10 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 11 ms 5504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 104 ms 62844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 124 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 66 ms 13564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 59 ms 13740 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 64 ms 14328 KB Execution killed with signal 11 (could be triggered by violating memory limits)