Submission #98843

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98843	2019-02-26T13:44:05 Z	fbosnjak	Deblo (COCI18_deblo)	C++14	90 / 90	345 ms	20956 KB

deblo

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll N;
ll val[100100], val_node[100100], a, b;
const ll maxn = 3e6;
vector <int> v[100100];
vector <int> graf[100100];
bool bio[100100];
ll sol = 0;
ll nula[100100], jedan[100100];
ll curr;

void make_tree(int x)
{
    bio[x] = 1;
    for (int i = 0; i < graf[x].size(); i++)
    {
        int next = graf[x][i];
        if (!bio[next])
        {
            v[x].push_back(next);
            make_tree(next);
        }
    }

    return;
}

void solve(int x)
{
    if (val_node[x] == 1) sol += curr;

    for (int i = 0; i < v[x].size(); i++)
    {
        int next = v[x][i];
        solve(next);

        if (val_node[x] == 1)
        {
            sol += (nula[next] * curr);
        }
        else
        {
            sol += (jedan[next] * curr);
        }
    }

    if (v[x].size() > 1)
    {
        jedan[x] = jedan[v[x][0]];
        nula[x] = nula[v[x][0]];

        for (int i = 1; i < v[x].size(); i++)
        {
            int next = v[x][i];
            if (val_node[x] == 1)
            {
                sol += (jedan[next] * jedan[x] * curr);
                sol += (nula[next] * nula[x] * curr);
            }
            else
            {
                sol += (jedan[next] * nula[x] * curr);
                sol += (nula[next] * jedan[x] * curr);
            }

            jedan[x] += jedan[next];
            nula[x] += nula[next];
        }
    }
    else
    {
        if (v[x].size() == 1)
        {
            jedan[x] = jedan[v[x][0]];
            nula[x] = nula[v[x][0]];
        }
    }

    if (val_node[x] == 1) swap(jedan[x], nula[x]);
    if (val_node[x] == 1) jedan[x]++;
    else nula[x]++;

    //cout << x << ' ' << sol << endl;

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> val[i];
    }

    for (int i = 1; i < N; i++)
    {
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    memset(bio, 0, sizeof bio);

    make_tree(1);

    for (int i = 1; i <= maxn; i *= 2)
    {
        curr = i;

        memset(val_node, 0, sizeof val_node);
        memset(nula, 0, sizeof nula);
        memset(jedan, 0, sizeof jedan);

        for (int j = 1; j <= N; j++)
        {
            if (val[j] & i) val_node[j] = 1;
        }

        solve(1);

        //cout << sol << endl;
    }

    cout << sol;
}

Compilation message

deblo.cpp: In function 'void make_tree(int)':
deblo.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < graf[x].size(); i++)
                     ~~^~~~~~~~~~~~~~~~
deblo.cpp: In function 'void solve(int)':
deblo.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v[x].size(); i++)
                     ~~^~~~~~~~~~~~~
deblo.cpp:56:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < v[x].size(); i++)
                         ~~^~~~~~~~~~~~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	7508 KB	Output is correct
2	Correct	13 ms	7424 KB	Output is correct
3	Correct	14 ms	7552 KB	Output is correct
4	Correct	13 ms	7552 KB	Output is correct
5	Correct	14 ms	7552 KB	Output is correct
6	Correct	264 ms	20956 KB	Output is correct
7	Correct	196 ms	20856 KB	Output is correct
8	Correct	267 ms	14720 KB	Output is correct
9	Correct	198 ms	14072 KB	Output is correct
10	Correct	345 ms	13176 KB	Output is correct