Submission #86100

#	Time	Username	Problem	Language	Result	Execution time	Memory
86100		Shtef	Deblo (COCI18_deblo)	C++14	90 / 90	463 ms	16920 KiB

deblo

#include <iostream>
#include <vector>
#include <utility>
#include <cstring>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
#define x first
#define y second
#define mp make_pair

ll a[100005], xo[100005], sol = 0;
vector <int> ms[100005];
pll vr[100005];
int n;

void dfs1(int x, int p){
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p)
			continue;
		xo[o] = xo[x] ^ a[o];
		dfs1(o, x);
	}
}

pll dfs2(int x, int p, int val){
	vr[x] = mp(bool(!(xo[x] & val)), bool(xo[x] & val));
	for(vector <int>::iterator i = ms[x].begin() ; i != ms[x].end() ; ++i){
		int o = *i;
		if(o == p)
			continue;
		pll t = dfs2(o, x, val);
		vr[x].x += t.x;
		vr[x].y += t.y;
		int x1 = vr[x].x - vr[o].x, y1 = vr[x].y - vr[o].y;
		if(a[x] & val){
			sol += (vr[o].x * x1 + vr[o].y * y1) * val;
		}
		else{
			sol += (vr[o].x * y1 + vr[o].y * x1) * val;
		}
	}
	return vr[x];
}

int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; ++i){
	cin >> a[i];
	sol += a[i];
}
for(int i = 0 ; i < n - 1 ; ++i){
	int x, y;
	cin >> x >> y;
	ms[x].push_back(y);
	ms[y].push_back(x);
}
xo[1] = a[1];
dfs1(1, -1);
//for(int i = 1 ; i <= n ; ++i){
//	cout << xo[i] << ' ';
//}
for(int i = 0 ; i <= 22 ; ++i){
	memset(vr, 0, sizeof(vr));
	dfs2(1, -1, (1 << i));
	//for(int j = 1 ; j <= n ; ++j){
	//	cout << vr[j].x << ' ' << vr[j].y << endl;
	//}
	//cout << endl;
}
cout << sol << endl;

return 0;
}

• Subtask 1: 90 / 90