Submission #765563

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
765563	2023-06-24T20:00:46 Z	DmitryKh	Deblo (COCI18_deblo)	C++14	45 / 90	1000 ms	65536 KB

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++) {
        bool bit_on = (A[v]>>i) & ll(0x1);
        for (auto u : E[v]) {
            if (!R[u].empty()) {
                if (bit_on) {
                    R[v][2*i + 1] += R[u][2*i];
                    R[v][2*i] += R[u][2*i + 1];
                } else {
                    R[v][2*i + 1] += R[u][2*i + 1];
                    R[v][2*i] += R[u][2*i];
                }
            }
        }

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

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

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

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

        rr += R[v][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

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:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   92 |         for (int j = 0; j < 8*sizeof(ll) - 1; j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1

45.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	3 ms	468 KB	Output is correct
4	Correct	19 ms	1492 KB	Output is correct
5	Correct	19 ms	1404 KB	Output is correct
6	Runtime error	122 ms	65536 KB	Execution killed with signal 9
7	Runtime error	115 ms	65536 KB	Execution killed with signal 9
8	Execution timed out	1084 ms	61016 KB	Time limit exceeded
9	Execution timed out	1091 ms	52296 KB	Time limit exceeded
10	Execution timed out	1088 ms	48028 KB	Time limit exceeded