oj.uz

Submission #197336

# Submission time Handle Problem Language Result Execution time Memory
197336 2020-01-20T12:30:12 Z quocnguyen1012 Deblo (COCI18_deblo) C++14
90 / 90
 146 ms 54904 KB 
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Task "A"
 
using namespace std;
typedef long long ll;
 
const int maxn = 1e5 + 5;
 
ll f[maxn][25][2];
int N, a[maxn];
vector<int> adj[maxn];
ll ans = 0;
 
bool testbit(int x, int n)
{
    return x >> n & 1;
}
 
void dfs(int u, int p = -1)
{
    for (int i=0; i<25; ++i){
        f[u][i][testbit(a[u], i)] = 1;
    }
    for (int v  : adj[u]){
        if (v != p){
            dfs(v, u);
            for (int i=0; i<25; ++i){
                ans += (1ll << i) * f[u][i][1] * f[v][i][0];
                ans += (1ll << i) * f[u][i][0] * f[v][i][1];
                if (testbit(a[u], i)){
                    f[u][i][0] += f[v][i][1];
                    f[u][i][1] += f[v][i][0];
                }
                else{
                    f[u][i][0] += f[v][i][0];
                    f[u][i][1] += f[v][i][1];
                }
            }
        }
    }
    ans += a[u];
}
 
signed main(void)
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")){
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }
    cin >> N;
    for (int i=1; i<=N; ++i){
        cin >> a[i];
    }
    for (int i=1; i<N; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dfs(1);
    cout << ans << '\n';
}

Compilation message

deblo.cpp: In function 'int main()':
deblo.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".INP", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
deblo.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".OUT", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 3196 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 114 ms 54776 KB Output is correct
7 Correct 112 ms 54904 KB Output is correct
8 Correct 111 ms 47228 KB Output is correct
9 Correct 114 ms 46292 KB Output is correct
10 Correct 146 ms 45560 KB Output is correct