oj.uz

Submission #92152

# Submission time Handle Problem Language Result Execution time Memory
92152 2019-01-01T18:07:57 Z Kastanda Deblo (COCI18_deblo) C++11
90 / 90
 212 ms 13816 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, A[N], C[N][2];
long long tot, cnt;
bool B[N];
vector < int > Adj[N];
void DFS(int v, int p)
{
    if (B[v]) cnt ++;
    C[v][0] = C[v][1] = 0;
    C[v][B[v]] ++;
    for (int &u : Adj[v])
        if (u != p)
        {
            DFS(u, v);
            cnt += 1LL * C[v][0] * C[u][1];
            cnt += 1LL * C[v][1] * C[u][0];
            C[v][0] += C[u][B[v]];
            C[v][1] += C[u][!B[v]];
        }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]);
    for (int i = 1, v, u; i < n; i++)
        scanf("%d%d", &v, &u),
        Adj[v].push_back(u),
        Adj[u].push_back(v);
    for (int j = 0; j <= 21; j++)
    {
        cnt = 0;
        for (int i = 1; i <= n; i++)
            B[i] = (A[i] >> j) & 1;
        DFS(1, 0);
        tot += cnt * (1LL << j);
    }
    return !printf("%lld", tot);
}

Compilation message

deblo.cpp: In function 'int main()':
deblo.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
deblo.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
deblo.cpp:30:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &v, &u),
         ~~~~~~~~~~~~~~~~~~~~~~~
         Adj[v].push_back(u),
         ~~~~~~~~~~~~~~~~~~~^~
         Adj[u].push_back(v);
         ~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2680 KB Output is correct
2 Correct 3 ms 2680 KB Output is correct
3 Correct 3 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 90 ms 13816 KB Output is correct
7 Correct 90 ms 13560 KB Output is correct
8 Correct 104 ms 9848 KB Output is correct
9 Correct 107 ms 9464 KB Output is correct
10 Correct 212 ms 9080 KB Output is correct