Submission #752140

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
752140	2023-06-02T10:55:55 Z	Neklixx	Deblo (COCI18_deblo)	C++17	90 / 90	364 ms	19580 KB

deblo

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define sh                  \
    cin.tie(0);             \
    cin.sync_with_stdio(0); \
    cout.tie(0);
#define FILE freopen("test.in", "r", stdin);
#define vprint(v)                           \
    for (int ii = 0; ii < v.size(); ii++) { \
        cout << v[ii] << " ";               \
    }
#define debugv(v)                                          \
    if (v.size() != 0) {                                   \
        cout << "[ ";                                      \
        for (int __ = 0; __ < (int)(v.size()) - 1; __++) { \
            cout << v[__] << ", ";                         \
        }                                                  \
        cout << v[(int)(v.size()) - 1] << " ]" << endl;    \
    } else {                                               \
        cout << "[]" << endl;                              \
    }
#define debug cout << "-----------------------------------------------" << endl;
#define print1(a) cout << "{ " << a << " }" << endl;
#define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl;
#define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl;
#define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl;
using namespace std;
#define int long long
const int INF = 1e9 + 228;
const int MAXN = 1e5 + 228;
const int MAXP = 24;

vector<int> a;
vector<int> g[MAXN];
bool used[MAXN];
bool used2[MAXN];
int dp[MAXN][2];

int dfs(int v, int pow)
{
    used[v] = 1;
    int val = (a[v] >> pow) % 2;
    int result = 0;
    dp[v][val] = 1;
    for (const auto& to : g[v]) {
        if (used[to]) {
            continue;
        }
        result += dfs(to, pow);
        dp[v][val ^ 1] += dp[to][1];
        dp[v][val ^ 0] += dp[to][0];
    }
    int tmp = 0;
    for (const auto& to : g[v]) {
        if (!used2[to]) {
            continue;
        }
        tmp += (dp[v][1] - dp[to][val ^ 1]) * dp[to][0];
        tmp += (dp[v][0] - dp[to][val ^ 0]) * dp[to][1];
    }
    tmp += dp[v][1];
    tmp -= val;
    tmp /= 2;
    tmp += val;
    result += tmp;
    // if (pow == 2) {
    // cout << v << ' ' << tmp << ' '  << dp[v][0] << ' ' << dp[v][1] << ' ' << pow << endl;
    // }
    used2[v] = 1;
    return result;
}

signed main()
{
#ifdef LOCAL
    FILE;
#else
    // freopen("next.in", "r", stdin);
    // freopen("next.out", "w", stdout);
#endif
    sh;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int aa;
        cin >> aa;
        a.pb(aa);
    }
    for (int i = 0; i < n - 1; ++i) {
        int aa, bb;
        cin >> aa >> bb;
        --aa;
        --bb;
        g[aa].pb(bb);
        g[bb].pb(aa);
    }
    int pow = 0;
    int ans = 0;
    for (int i = 0; i < 24; ++i) {
        for (int j = 0; j < n; ++j) {
            used[j] = 0;
            used2[j] = 0;
            dp[j][0] = dp[j][1] = 0;
        }
        int tmp = dfs(0, pow);
        ans += (tmp << pow);
        ++pow;
    }
    cout << ans << endl;
    return 0;
}

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2644 KB	Output is correct
3	Correct	2 ms	2644 KB	Output is correct
4	Correct	3 ms	2748 KB	Output is correct
5	Correct	3 ms	2772 KB	Output is correct
6	Correct	124 ms	19580 KB	Output is correct
7	Correct	130 ms	19576 KB	Output is correct
8	Correct	111 ms	12408 KB	Output is correct
9	Correct	137 ms	11600 KB	Output is correct
10	Correct	364 ms	10772 KB	Output is correct