Submission #311751

#	Time	Username	Problem	Language	Result	Execution time	Memory
311751		neki	Deblo (COCI18_deblo)	C++14	90 / 90	580 ms	24152 KiB

deblo

#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 / 90