oj.uz

Submission #228957

# Submission time Handle Problem Language Result Execution time Memory
228957 2020-05-03T07:29:50 Z kartel Deblo (COCI18_deblo) C++14
0 / 90
 160 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, 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 += (1 << bt) * f[v][bt][0] * f[u][bt][1];
            ans += (1 << 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 5 ms 2688 KB Output isn't correct
3 Runtime error 11 ms 5504 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 11 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 150 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 160 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 61 ms 12664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 61 ms 12664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 58 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)