oj.uz

Submission #311751

# Submission time Handle Problem Language Result Execution time Memory
311751 2020-10-11T13:07:08 Z neki Deblo (COCI18_deblo) C++14
90 / 90
 580 ms 24152 KB 
#include <bits/stdc++.h>
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 200100
#define pa pair<ll, ll>
#define ld long double
ll arr[mn], val[mn], sum=0;
ll dp[mn][2];
vc<ll> edg[mn];
void dfs(ll u, ll p){
    ll cnt[2];cnt[0]=0, cnt[1]=0;
    dp[u][0]=0, dp[u][1]=0;
    fore(v, edg[u]) if(v!=p){
        dfs(v, u);
        cnt[0]+=dp[v][0];
        cnt[1]+=dp[v][1];
    }
    fore(v, edg[u]) if(v!=p){
        loop(x, 0, 2){
            loop(y, 0, 2){
                sum+=(cnt[x]-dp[v][x]) * (dp[v][y]) * (x xor y xor val[u]);
            }
        }
    }
    dp[u][val[u] xor 0]=cnt[0];
    dp[u][val[u] xor 1]=cnt[1];
    dp[u][val[u]]++;
    sum+=2 * dp[u][1];
}
int main(){
    ll n;cin >> n;
    loop(i, 1, n+1) cin >> arr[i];
    loop(i, 0, n-1){
        ll a, b;cin >> a >> b;
        edg[a].ps(b);
        edg[b].ps(a);
    }
    ll ans=0;
    loop(i, 0, 23){
        sum=0;
        loop(j, 1, n+1) val[j]=((arr[j]&(1<<i))!=0);
        dfs(1, -1);
        ans+=(1<<i) * sum;
    }
    cout << ans/2 <<endl;
}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5056 KB Output is correct
6 Correct 316 ms 24152 KB Output is correct
7 Correct 323 ms 24088 KB Output is correct
8 Correct 287 ms 15720 KB Output is correct
9 Correct 313 ms 14712 KB Output is correct
10 Correct 580 ms 13816 KB Output is correct