Submission #701742

#	Time	Username	Problem	Language	Result	Execution time	Memory
701742		chenyan	Deblo (COCI18_deblo)	C++17	90 / 90	148 ms	56168 KiB

deblo

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define N 200010
vector<int>c[N];
bitset<N>vis;
int a[N],ans,dp[30][2][N];
void dfs(int v){
	vis[v]=1;
	int i;
	ans+=a[v];
	for(i=0;i<25;i++)
		dp[i][(a[v]>>i)&1][v]++;
	for(int u:c[v]){
		if(vis[u])continue;
		dfs(u);
		for(i=0;i<25;i++){
			ans+=(dp[i][0][v]*dp[i][1][u]+dp[i][1][v]*dp[i][0][u])*(1<<i);
			dp[i][0][v]+=dp[i][(a[v]>>i)&1][u];
			dp[i][1][v]+=dp[i][(a[v]>>i)&1^1][u];
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int u,v,n,m,i,j,k;
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=0;i<n-1;i++){
		cin>>u>>v;
		c[u].pb(v);
		c[v].pb(u);
	}
	dfs(1);
	cout<<ans<<'\n';
}

Compilation message (stderr)

deblo.cpp: In function 'void dfs(long long int)':
deblo.cpp:25:32: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   25 |    dp[i][1][v]+=dp[i][(a[v]>>i)&1^1][u];
      |                       ~~~~~~~~~^~
deblo.cpp: In function 'int main()':
deblo.cpp:32:12: warning: unused variable 'm' [-Wunused-variable]
   32 |  int u,v,n,m,i,j,k;
      |            ^
deblo.cpp:32:16: warning: unused variable 'j' [-Wunused-variable]
   32 |  int u,v,n,m,i,j,k;
      |                ^
deblo.cpp:32:18: warning: unused variable 'k' [-Wunused-variable]
   32 |  int u,v,n,m,i,j,k;
      |                  ^

• Subtask 1: 90 / 90