Submission #778441

#	Time	Username	Problem	Language	Result	Execution time	Memory
778441		vjudge1	Deblo (COCI18_deblo)	C++17	90 / 90	85 ms	55052 KiB

deblo

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define OYY 1000000005
#define mod 998244353
#define mid (start+end)/2
int dizi[100005],n,cev=0;
vector <int> v[100005];
int dp[100005][25][2];

//// left-shifting an integer “a” with an integer “b” denoted as ‘(a<<b)’ is equivalent to multiplying a with 2^b
//// right-shifting an integer “a” with an integer “b” denoted as ‘(a>>b)‘ is equivalent to dividing a with 2^b.
//// a=a/(2^b)

inline int fast(int x,int y){
    int ans=1;
    x%=mod;
    while(y!=0){
        if(y&1!=0)ans*=x;
        x*=x;
        y>>=1;
    }
    return ans;
}

inline void dfs(int node,int ata){
    for(int i=0;i<23;i++) { // power of 23
        if((dizi[node]>>i)%2==1)dp[node][i][1]=1;
        else dp[node][i][0]=1;
    }
    /*for(int i=0;i<20;i++){
        cout<<dp[node][i][0]<<" "<<dp[node][i][1]<<endl;
    }*/
    for(int i=0;i<v[node].size();i++){
        int go=v[node][i];
        if(go==ata)continue;
        dfs(go,node);
        for(int j=0;j<23;j++){
            int l=dp[go][j][1];
            int r=dp[go][j][0];
   //         int hu=max(l*dp[node][j][0],r*dp[node][j][1]);
            int hu=(l*dp[node][j][0]+r*dp[node][j][1]);
            //cev+=hu;//
            cev+=(hu<<j);
           /* int gec=(hu<<j);
            cout<<gec<<endl;*/
            int k=(dizi[node]>>j)&1;
            //cout<<k<<endl;

            dp[node][j][k]+=r;
            dp[node][j][k^1]+=l;
            //cout<<dp[node][j][k]<<" "<<dp[node][j][k^1]<<endl;
        }
    }
}

int32_t main(){
    faster
    cin>>n;
    int c=0;
    for(int i=1;i<=n;i++){
        cin>>dizi[i];
        cev+=dizi[i];
    }
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,-1);
    cout<<cev<<'\n';
    return 0;
}

Compilation message (stderr)

deblo.cpp: In function 'long long int fast(long long int, long long int)':
deblo.cpp:20:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   20 |         if(y&1!=0)ans*=x;
      |              ~^~~
deblo.cpp: In function 'void dfs(long long int, long long int)':
deblo.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<v[node].size();i++){
      |                 ~^~~~~~~~~~~~~~~
deblo.cpp: In function 'int32_t main()':
deblo.cpp:61:9: warning: unused variable 'c' [-Wunused-variable]
   61 |     int c=0;
      |         ^

• Subtask 1: 90 / 90