Submission #765571

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765571	2023-06-24T20:31:51 Z	DmitryKh	Deblo (COCI18_deblo)	C++14	90 / 90	142 ms	47152 KB

deblo

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

using namespace std;
using ll = long long;
using llr = int;

ll DFS(int v,
       const vector<vector<int>>& E,
       const vector<ll>& A,
       vector<bool>& VIS,
       llr maxBitMask,
       vector<llr>& R) {
    ll rr = 0;
    VIS[v] = true;
    vector<vector<llr>> RN(E[v].size());
    for (int i = 0; i < E[v].size(); i++) {
        int u = E[v][i];
        if (!VIS[u]) {
            RN[i].resize((maxBitMask + 1)*2);
            rr += DFS(u, E, A, VIS, maxBitMask, RN[i]);
        }
    }

    //cout << "v[" << v << "]:\n";
    for (int i = 0; i < maxBitMask + 1; i++) {
        bool bit_on = (A[v]>>i) & ll(0x1);
        for (int j = 0; j < RN.size(); j++) {
            if (!RN[j].empty()) {
                if (bit_on) {
                    R[2*i + 1] += RN[j][2*i];
                    R[2*i] += RN[j][2*i + 1];
                } else {
                    R[2*i + 1] += RN[j][2*i + 1];
                    R[2*i] += RN[j][2*i];
                }
            }
        }

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

        ll arc1 = 0;
        for (int j = 0; j < RN.size(); j++) {
            if (!RN[j].empty()) {
                if (bit_on) {
                    if (RN[j][2*i + 1] && RN[j][2*i + 1]*(r0 - RN[j][2*i + 1]) > 0) {
                        arc1 += RN[j][2*i + 1]*(r0 - RN[j][2*i + 1]);
                    }

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

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

        rr += ll(R[2*i + 1])*(ll(1)<<i) + (arc1/2)*(ll(1)<<i);
    }
    
    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';
        vector<llr> R((maxBitMask + 1)*2);
        {
            vector<bool> VIS(n + 1);
            cout << DFS(1, E, A, VIS, maxBitMask, R) << '\n';
        }
    }

    return 0;
}

Compilation message

deblo.cpp: In function 'll DFS(int, const std::vector<std::vector<int> >&, const std::vector<long long int>&, std::vector<bool>&, llr, std::vector<int>&)':
deblo.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < E[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
deblo.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j = 0; j < RN.size(); j++) {
      |                         ~~^~~~~~~~~~~
deblo.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int j = 0; j < RN.size(); j++) {
      |                         ~~^~~~~~~~~~~
deblo.cpp: In function 'int main(int, char**)':
deblo.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   88 |         for (int j = 0; j < 8*sizeof(ll) - 1; j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	139 ms	47152 KB	Output is correct
7	Correct	142 ms	45808 KB	Output is correct
8	Correct	131 ms	15776 KB	Output is correct
9	Correct	130 ms	11468 KB	Output is correct
10	Correct	131 ms	6692 KB	Output is correct