Submission #329143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329143	2020-11-19T13:08:52 Z	monus1042	Deblo (COCI18_deblo)	C++17	63 / 90	69 ms	9448 KB

deblo

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

typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define psf push_front
#define pof pop_front
#define mkp make_pair
#define mkt make_tuple
#define all(x) x.begin(), x.end()
#define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr)

const int MAXS = 1e5+5;
const int LOG = 18;
vi g[MAXS];

int n;
vll ve;

int lca[MAXS][LOG];
int dp[MAXS][LOG];
int lev[MAXS];

void dfs(int u, int p, int le){
	lev[u] = le;
	lca[u][0] = p;
	dp[u][0] = (int)ve[p]; ///////
	
	int node = p;
	for (int i=1; i<LOG; ++i){
		lca[u][i] = lca[node][i-1];
		dp[u][i] = dp[u][i-1] ^ dp[node][i-1];
		node = lca[node][i-1];
	}

	for (int i=0; i<g[u].size(); ++i){
		int v = g[u][i];
		if (v != p){
			dfs(v, u, le+1);
		}
	}
}

void climb(int dist, int & A, int & B, int & ret){
	for (int i=0; i<LOG; ++i){
		if (dist & (1 << i)){
			ret ^= dp[A][i];
			A = lca[A][i];
		}
	}
}

int que(int A, int B){
	int ret = 0;
	if (lev[A] < lev[B]) swap(A,B);
	ret = (int)ve[A];
	int dist = lev[A] - lev[B];
	climb(dist, A, B, ret);
	if (A == B) return ret;
	ret ^= (int)ve[B];
	for (int i=LOG-1; ~i; --i){
		if (lca[A][i] != lca[B][i]){
			ret ^= dp[A][i];
			ret ^= dp[B][i];
			A = lca[A][i];
			B = lca[B][i];
		}
	}
	int upwards = lca[A][0];
	ret ^= (int)ve[upwards];
	return ret;
}


void sb(){
	dfs(1, 0, 0);
	ll ans = 0;
	for (int i=1; i<=n; ++i) ans += ve[i];
	for (int i=1; i<=n - 1; ++i){
		for (int j=i+1; j<=n; ++j){
			int Q = que(i,j);
			ans = ans + (ll)Q;
		}
	}
	cout << ans << '\n';
}

void subeasy(){
	vll pre(n+2);
	for (int i=1; i<=n; ++i) pre[i] = pre[i-1] ^ ve[i];

	ll ans = 0;
	//for (int i=1; i<=n; ++i) ans += acc[i];

	for (int i=0; i<=30; ++i){
		ll zeros = 1, ones = 0;
		ll ithset = 0;
		for (int j=1; j<=n; ++j){
			if ((1<<i) & pre[j]){
				ithset += (ll)zeros;
				ones++;
			}else{
				ithset += (ll)ones;
				zeros++;
			}
		}
		ll aux = (1LL << i) * ithset;
		ans += aux;
	}
	cout << ans << '\n';
}

void solve(){
	cin >> n;
	for (int i=0; i<n; ++i){
		ll x; cin >> x;
		ve.pb(x);
	}
	ve.insert(ve.begin(), 1, 0);
	for (int i=0; i<n-1; ++i){
		int u,v; cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	
	if (n <= 1000){
		sb();
	}else{
		subeasy();
	}
}

int main(){
	Bolivia_is_nice;
	int t = 1; //cin>>t;
	while(t--)
	solve();
	
	return 0;
}
/*
  ~/.emacs
*/

Compilation message

deblo.cpp: In function 'void dfs(int, int, int)':
deblo.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i=0; i<g[u].size(); ++i){
      |                ~^~~~~~~~~~~~

Subtask #1

63.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	2 ms	2668 KB	Output is correct
3	Correct	3 ms	2816 KB	Output is correct
4	Correct	40 ms	2924 KB	Output is correct
5	Correct	44 ms	2924 KB	Output is correct
6	Correct	54 ms	9340 KB	Output is correct
7	Correct	55 ms	9448 KB	Output is correct
8	Incorrect	56 ms	9320 KB	Output isn't correct
9	Incorrect	69 ms	9448 KB	Output isn't correct
10	Incorrect	61 ms	9320 KB	Output isn't correct