Submission #890293

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
890293	2023-12-21T01:08:55 Z	pcc	Deblo (COCI18_deblo)	C++14	36 / 90	105 ms	18444 KB

deblo

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

#define int ll

const int mxn = 1e5+10;
vector<int> tree[mxn];
int val[mxn],dp[mxn][2],arr[mxn];
int n;
ll ans = 0;

void dfs(int now,int par,int bit){
	dp[now][0] = dp[now][1] = 0;
	dp[now][(arr[now]&(1<<bit)?1:0)] = 1;
	val[now] = (arr[now]&(1<<bit)?1:0);
	for(auto nxt:tree[now]){
		if(nxt == par)continue;
		dfs(nxt,now,bit);
		ans += 1ll*dp[now][1]*dp[nxt][0]*(1<<bit);
		ans += 1ll*dp[now][0]*dp[nxt][1]*(1<<bit);
		dp[now][val[now]] += dp[nxt][0];
		dp[now][val[now]^1] += dp[nxt][1];
	}
	return;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>arr[i];
	for(int i = 1;i<n;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 0;i<20;i++){
		dfs(1,1,i);
	}
	for(int i = 1;i<=n;i++)ans += arr[i];
	cout<<ans;
}

Compilation message

deblo.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      | ^~~~

Subtask #1

36.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5720 KB	Output is correct
2	Correct	1 ms	5724 KB	Output is correct
3	Incorrect	1 ms	5724 KB	Output isn't correct
4	Incorrect	2 ms	5724 KB	Output isn't correct
5	Incorrect	3 ms	5724 KB	Output isn't correct
6	Incorrect	68 ms	18444 KB	Output isn't correct
7	Correct	67 ms	18232 KB	Output is correct
8	Incorrect	65 ms	11100 KB	Output isn't correct
9	Incorrect	67 ms	10320 KB	Output isn't correct
10	Correct	105 ms	9564 KB	Output is correct