Submission #791277

#	Time	Username	Problem	Language	Result	Execution time	Memory
791277		BidoTeima	Deblo (COCI18_deblo)	C++17	90 / 90	236 ms	23016 KiB

deblo

#include <bits/stdc++.h>
typedef long long ll;
using namespace std; 
const int N = 1e5 + 3;
vector<int>adj_1[N],adj[N];
bool a[N];
int arr[N];
ll dp[2][N];
void direct(int node, int prev){
    if(prev != -1){
        adj[prev].push_back(node);
    }
    for(int child : adj_1[node]){
        if(child != prev){
            direct(child, node);
        }
    }
}
ll dfs(int node, bool b){
    if(dp[b][node] != -1)
        return dp[b][node]; 
    ll ret = a[node] == b;
    for(int child : adj[node]){
        ret += dfs(child, b ^ a[node]);
    }
    //cout<<b<<' '<<node<<' '<<ret<<'\n';
    return dp[b][node] = ret;
}
int main() {    
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>arr[i];
    for(int i = 1; i < n; i++){
        int a,b;
        cin>>a>>b;
        adj_1[a].push_back(b);
        adj_1[b].push_back(a);
    }
    direct(1,-1);
    ll ans = 0;
    for(int i = 0; (1 << i) < 3e6; i++){
        //cout<<"FOR THE "<<i<<"-TH BIT:\n";
        //cout<<"a: ";
        memset(dp, -1, sizeof(dp));
        for(int j = 1; j <= n; j++){
            a[j]=!!(arr[j]&(1<<i));
            //cout<<a[j]<<' ';
        }
       // cout<<'\n';
        for(int j = 1; j <= n; j++){  
            ll tot0=0,tot1=0;
            for(int child : adj[j]){
                tot0 += dfs(child, 0);
                tot1 += dfs(child, 1);
            }
            ll res = 0;
            for(int child : adj[j]){
                ll cnt0 = dfs(child, 0);
                ll cnt1 = dfs(child, 1);
                if(a[j]){
                    res += cnt0 * (tot0 - cnt0) + cnt1 * (tot1 - cnt1);
                }else{
                    res += cnt0 * (tot1 - cnt1) + cnt1 * (tot0 - cnt0);
                }
            }
            //cout<<j<<": "<<tot0<<' '<<tot1<<'\n';
            ans += (res / 2 + (a[j] ? tot0 : tot1) + (a[j]==1)) * (1ll << i);
            
        }
        //cout<<ans<<'\n';
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 90 / 90