oj.uz

Submission #342297

# Submission time Handle Problem Language Result Execution time Memory
342297 2021-01-01T18:58:39 Z Hazem Deblo (COCI18_deblo) C++14
90 / 90
 140 ms 36332 KB 
/*
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];
            if(vals[i]&(1<<j))freq[x][j] = sizes[x]-freq[x][j];
            
            ans += 1ll*(sizes[x]-freq[x][j])*(freq[i][j])*(1<<j)+1ll*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)continue;
        sizes[i] += sizes[x];
        for(int j=0;j<30;j++)
            freq[i][j] += freq[x][j];
    }
 
    return ;
}
 
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

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

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 8 ms 9964 KB Output is correct
5 Correct 8 ms 9836 KB Output is correct
6 Correct 101 ms 36332 KB Output is correct
7 Correct 99 ms 36332 KB Output is correct
8 Correct 103 ms 28652 KB Output is correct
9 Correct 104 ms 27884 KB Output is correct
10 Correct 140 ms 27116 KB Output is correct