oj.uz

Submission #701742

# Submission time Handle Problem Language Result Execution time Memory
701742 2023-02-22T03:17:28 Z chenyan Deblo (COCI18_deblo) C++17
90 / 90
 148 ms 56168 KB 
#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

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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5332 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 74 ms 56168 KB Output is correct
7 Correct 72 ms 56156 KB Output is correct
8 Correct 72 ms 50228 KB Output is correct
9 Correct 77 ms 49536 KB Output is correct
10 Correct 148 ms 49144 KB Output is correct