oj.uz

답안 #228956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
228956 2020-05-03T07:29:10 Z kartel Deblo (COCI18_deblo) C++14
0 / 90
 159 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;

ll n, i, x, y, a[N], 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

# 결과 실행 시간 메모리 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 5608 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 153 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 159 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 57 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 57 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 65 ms 14352 KB Execution killed with signal 11 (could be triggered by violating memory limits)