Submission #1284550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284550		aren_dance	Deblo (COCI18_deblo)	C++20	90 / 90	129 ms	42672 KiB

deblo

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int N=1e5+1;
vector<int> g[N];
ll dp[N];
ll answ;
ll a[N];
ll pref[N];
int cnt[N][31][2];
int n;
void dfs(int v,int p){
    pref[v]=pref[p]^a[v];
    for(int j=0;j<30;++j){
        if(pref[v]&(1<<j)){
            cnt[v][j][1]++;
        }
        else{
            cnt[v][j][0]++;
        }
    }
    for(auto i:g[v]){
        if(i==p){
            continue;
        }
        dfs(i,v);
        for(int j=0;j<30;++j){
            cnt[v][j][1]+=cnt[i][j][1];
            cnt[v][j][0]+=cnt[i][j][0];
        }
    }
    ll cntz[2];
    for(int j=0;j<30;++j){
        cntz[0]=0;
        cntz[1]=0;
        ll u=(1<<j);
        for(auto i:g[v]){
            if(i==p){
                continue;
            }
            if(((1<<j)&a[v])){
                ll e=cnt[i][j][0];
                answ+=cntz[0]*e*u;
                e=cnt[i][j][1];
                answ+=cntz[1]*e*u;
            }
            else{
                ll e=cnt[i][j][1];
                answ+=cntz[0]*e*u;
                e=cnt[i][j][0];
                answ+=cntz[1]*e*u;
            }
            cntz[0]+=cnt[i][j][0];
            cntz[1]+=cnt[i][j][1];
        }
        if(((1<<j)&pref[p])){
            answ+=cntz[0]*u;
        }
        else{
            answ+=cntz[1]*u;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        answ+=a[i];
    }
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    cout<<answ<<'\n';
    return 0;
}

• Subtask 1: 90 / 90