oj.uz

Submission #765562

# Submission time Handle Problem Language Result Execution time Memory
765562 2023-06-24T19:50:25 Z DmitryKh Deblo (COCI18_deblo) C++14
72 / 90
 402 ms 65536 KB 
#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,
       vector<ll>& R) {
    ll rr = 0;
    VIS[v] = true;
    map<int, vector<ll>> RN;
    for (int i = 0; i < E[v].size(); i++) {
        int u = E[v][i] ;
        if (!VIS[u]) {
            RN[i].resize(16*sizeof(ll));
            rr += DFS(u, E, A, VIS, maxBitMask, RN[i]);
        }
    }

    //cout << "v[" << v << "]:\n";
    for (int i = 0; i < 8*sizeof(ll) - 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 += R[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';
        vector<ll> R(16*sizeof(ll));
        {
            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>&, ll, std::vector<long long int>&)':
deblo.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i = 0; i < E[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
deblo.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   27 |     for (int i = 0; i < 8*sizeof(ll) - 1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
deblo.cpp:29:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int j = 0; j < RN.size(); j++) {
      |                         ~~^~~~~~~~~~~
deblo.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int j = 0; j < RN.size(); j++) {
      |                         ~~^~~~~~~~~~~
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
72.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 300 KB Output is correct
4 Correct 4 ms 956 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Runtime error 115 ms 65536 KB Execution killed with signal 9
7 Runtime error 109 ms 65536 KB Execution killed with signal 9
8 Correct 402 ms 45456 KB Output is correct
9 Correct 374 ms 27892 KB Output is correct
10 Correct 369 ms 8524 KB Output is correct