Submission #342243

#	Time	Username	Problem	Language	Result	Execution time	Memory
342243		Hazem	Deblo (COCI18_deblo)	C++14	0 / 90	138 ms	38340 KiB

deblo

/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 2e5+10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

int vals[N],par[N][30],sizes[N];
LL pr[N],ans;
vector<int>adj[N];
vector<int>freq[N];

void dfs(int i,int pre){

    sizes[i] = 1;
    freq[i] = vector<int>(30,0);
    pr[i] = pr[pre]^vals[i];
    
    for(int j=0;j<30;j++)
        freq[i][j] += (pr[i]&(1<<j))!=0;

    for(auto x:adj[i]){
        if(x==pre)continue;
        dfs(x,i);
        sizes[i] += sizes[x];

        for(int j=0;j<30;j++)
            freq[i][j] += freq[x][j];
    }


    for(auto x:adj[i]){

        if(x==pre)continue;
        sizes[i] -= sizes[x];
        for(int j=0;j<30;j++)
            freq[i][j] -= freq[x][j];

        for(int j=0;j<30;j++){
            if(vals[i]&(1<<j))freq[x][j] = sizes[x]-freq[x][j];
            ans += (sizes[x]-freq[x][j])*(freq[i][j])*(1<<j)+freq[x][j]*(sizes[i]-freq[i][j])*(1<<j);
            if(vals[i]&(1<<j))freq[x][j] = sizes[x]-freq[x][j];
        }
    }

    for(auto x:adj[i])
        if(x!=pre)
        for(int j=0;j<30;j++)
            freq[i][j] += freq[x][j];

    // pr[i] = pr[pre]^vals[i];
    // par[i][0] = pre;
    // for(int j=1;j<=20;j++)
    //     par[i][j] = par[par[i][j-1]][j-1];
    // for(auto x:adj[i])
    //     if(x!=pre)depth[x] = depth[i]+1,dfs(x,i);
}

// int lca(int u,int v){

//     if(depth[u]<depth[v])swap(u,v);

//     for(int i=20;i>=0;i--)
//         if(depth[u]-(1<<i)>=depth[v])
//             u = par[u][i];

//     if(u==v)return u;

//     for(int i=20;i>=0;i--)
//         if(par[u][i]!=par[v][i])
//             u = par[u][i],v = par[v][i];

//     return par[u][0];
// }

int main()
{
    // freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        scanf("%d",&vals[i]),ans += vals[i];

    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1,1);

    printf("%lld\n",ans);
}       

Compilation message (stderr)

deblo.cpp: In function 'int main()':
deblo.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
deblo.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |         scanf("%d",&vals[i]),ans += vals[i];
      |         ~~~~~^~~~~~~~~~~~~~~
deblo.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 90