oj.uz

Submission #228955

# Submission time Handle Problem Language Result Execution time Memory
228955 2020-05-03T07:27:06 Z kartel Deblo (COCI18_deblo) C++14
0 / 90
 163 ms 65544 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;

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

void dfs(int v, int pr)
{
    for (int bt = 0; bt <= 25; 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 <= 25; 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 6 ms 2688 KB Output isn't correct
3 Runtime error 11 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 11 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 163 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 100 ms 65544 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 62 ms 13412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 61 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 61 ms 14328 KB Execution killed with signal 11 (could be triggered by violating memory limits)