Submission #765564

#	Time	Username	Problem	Language	Result	Execution time	Memory
765564		DmitryKh	Deblo (COCI18_deblo)	C++14	45 / 90	661 ms	65536 KiB

deblo

#include <iostream>
#include <vector>
#include <list>
#include <map>

using namespace std;
using ll = long long;

ll DFS(int v,
       const vector<vector<int>>& E,
       const vector<ll>& A,
       vector<bool>& VIS,
       ll maxBitMask,
       map<int, vector<ll>>& R) {
    ll rr = 0;
    VIS[v] = true;
    R[v].resize(16*sizeof(ll));
    for (auto u : E[v]) {
        if (!VIS[u]) {
            rr += DFS(u, E, A, VIS, maxBitMask, R);
        }
    }

    for (int i = 0; i < 8*sizeof(ll) - 1; i++) {
        auto& RV = R[v];
        bool bit_on = (A[v]>>i) & ll(0x1);
        for (auto u : E[v]) {
            auto& RU = R[u];
            if (!RU.empty()) {
                if (bit_on) {
                    RV[2*i + 1] += RU[2*i];
                    RV[2*i] += RU[2*i + 1];
                } else {
                    RV[2*i + 1] += RU[2*i + 1];
                    RV[2*i] += RU[2*i];
                }
            }
        }

        ll r0 = RV[2*i];
        ll r1 = RV[2*i + 1];
        if (bit_on) {
            RV[2*i + 1]++;
        } else {
            if (i <= maxBitMask) {
                RV[2*i]++;
            }
        }

        ll arc1 = 0;
        for (auto u : E[v]) {
            auto& RU = R[u];
            if (!RU.empty()) {
                if (bit_on) {
                    if (RU[2*i + 1] && R[u][2*i + 1]*(r0 - R[u][2*i + 1]) > 0) {
                        arc1 += RU[2*i + 1]*(r0 - R[u][2*i + 1]);
                    }

                    if (RU[2*i] && R[u][2*i]*(r1 - R[u][2*i]) > 0) {
                        arc1 += RU[2*i]*(r1 - R[u][2*i]);
                    }
                } else {
                    if (RU[2*i] && R[u][2*i]*(r1 - R[u][2*i + 1]) > 0) {
                        arc1 += RU[2*i]*(r1 - R[u][2*i + 1]);
                    }

                    if (RU[2*i + 1] && R[u][2*i + 1]*(r0 - R[u][2*i]) > 0) {
                        arc1 += RU[2*i + 1]*(r0 - R[u][2*i]);
                    }
                }
            }
        }

        rr += RV[2*i + 1]*(ll(1)<<i) + (arc1/2)*(ll(1)<<i);

        /*if (arc1)
            cout << "\tarc" << i << "=" << ((arc1/2)*(ll(1)<<i)) << '\n';
        if (R[2*i])
            cout << "\t" << i << "(0)=" << R[2*i] << '\n';
        if (R[2*i + 1])
            cout << "\t" << i << "(1)=" << R[2*i + 1] << '\n';*/
    }
    
    //cout << "v[" << v << "] = " << rr << '\n';
    return rr;
}

int main(int argc, char* argv[]) {
    int n;
    cin >> n;
    vector<ll> A(n + 1);
    ll maxBitMask = 0;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        for (int j = 0; j < 8*sizeof(ll) - 1; j++) {
            if (((A[i]>>j) & ll(0x1)) && j > maxBitMask) {
                maxBitMask = j;
            }
        }
    }

    vector<vector<int>> E(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    {
        //cout << '\n';
        map<int, vector<ll>> R;
        {
            vector<bool> VIS(n + 1);
            cout << DFS(1, E, A, VIS, maxBitMask, R) << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

deblo.cpp: In function 'll DFS(int, const std::vector<std::vector<int> >&, const std::vector<long long int>&, std::vector<bool>&, ll, std::map<int, std::vector<long long int> >&)':
deblo.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   24 |     for (int i = 0; i < 8*sizeof(ll) - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
deblo.cpp: In function 'int main(int, char**)':
deblo.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   95 |         for (int j = 0; j < 8*sizeof(ll) - 1; j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 45 / 90