Submission #229036

#	Time	Username	Problem	Language	Result	Execution time	Memory
229036		Vimmer	Deblo (COCI18_deblo)	C++14	18 / 90	1087 ms	13196 KiB

deblo

#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) ll(x.size())
#define pb push_back
#define N 100005
#define MOD ll(998244353)

using namespace std;

//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;

typedef short int si;

//typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;


int a[N], n, siz[N], t;

ll kol[23][2], st[23], sum, koler;

bool mk[N];

ll ans = 0;

vector <int> g[N];

void add(int x)
{
    int v = 0;

    while (x > 0)
    {
        if (x % 2) kol[v][1]++;
          else kol[v][0]++;

        x /= 2;

        v++;
    }

    while (v < 23) {kol[v][0]++; v++;}
}

void dec(int x)
{
    int v = 0;

    while (x > 0)
    {
        if (x % 2) kol[v][1]--;
          else kol[v][0]--;
        x /= 2;

        v++;
    }

    while (v < 23) {kol[v][0]--; v++;}
}

void dfs(int v, int p)
{
    siz[v] = 1;

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        dfs(it, v);

        siz[v] += siz[it];
    }
}
int fnd_cent(int v, int p)
{
    if (p != -1) {siz[p] -= siz[v]; siz[v] += siz[p];}

    bool gd = 1;

    for (auto it : g[v]) if (siz[it] > siz[v] / 2) {gd = 0; break;}

    if (gd) return v;

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        int root = fnd_cent(it, v);

        if (root != -1) return root;
    }

    return -1;
}

void spusk(int v, int p)
{
    koler++;

    t ^= a[v];

    add(t);

    ans += t;

    sum += t;

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        spusk(it, v);
    }

    t ^= a[v];
}
void spusk_dec(int v, int p)
{
    koler++;

    t ^= a[v];

    dec(t);

    sum -= t;

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        spusk_dec(it, v);
    }

    t ^= a[v];
}

void calcer(int x, bool f)
{
    int v = 0;

    while (x > 0)
    {
        if (x % 2)
        {
            if (f)
            {
                sum -= kol[v][0] * st[v];

                sum += kol[v][1] * st[v];
            }
            else
            {
                sum += kol[v][0] * st[v];

                sum -= kol[v][1] * st[v];
            }
        }

        x /= 2;

        v++;
    }
}

void swp(int x)
{
    int v = 0;

    while (x > 0)
    {
        if (x % 2) swap(kol[v][0], kol[v][1]);

        v++;

        x /= 2;
    }
}
void dfs_calc(int v, int p)
{
    calcer(a[v], 0);

    ans += sum;

    swp(a[v]);

    for (auto it : g[v])
    {
        if (it == p || mk[it]) continue;

        dfs_calc(it, v);
    }

    swp(a[v]);

    calcer(a[v], 1);
}
void calc(int v)
{
    mk[v] = 1;

    memset(kol, 0, sizeof(kol));

    sum = 0;

    koler = 0;

    for (auto it : g[v])
    {
        if (mk[it]) continue;

        t = a[v];

        spusk(it, -1);
    }

    for (auto it : g[v])
    {
        if (mk[it]) continue;

        t = a[v];

        spusk_dec(it, -1);

        dfs_calc(it, -1);
    }

    for (auto it : g[v])
    {
        if (mk[it]) continue;

        dfs(it, -1);

        int root = fnd_cent(it, -1);

        if (root != -1) calc(root);
    }
}

int main()
{
   // freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    st[0] = 1;

    for (int i = 1; i < 23; i++) st[i] = st[i - 1] * 2;

    for (int i = 1; i < n; i++)
    {
        int a, b;

        cin >> a >> b;

        a--; b--;

        g[a].pb(b); g[b].pb(a);
    }

    dfs(0, -1);

    int root = fnd_cent(0, -1);

    calc(root);

    for (int i = 0; i < n; i++) ans += ll(a[i]);

    cout << ans << endl;
}

• Subtask 1: 18 / 90