Submission #329092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329092	2020-11-19T02:00:17 Z	monus1042	Deblo (COCI18_deblo)	C++17	45 / 90	55 ms	10216 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];
			//cout << '\t' << dp[A][i] << endl;
			A = lca[A][i];
		}
	}
}

int que(int A, int B){
	int ret = 0;
	if (lev[A] < lev[B]) swap(A,B);
	//cout << A << ' ' << lev[A] << ' ' << B << ' ' << lev[B] << endl;
	ret = (int)ve[A];
	//cout << ret << endl;
	int dist = lev[A] - lev[B];
	climb(dist, A, B, ret);
	//cout << endl;
	//cout << ret << endl << dist << endl<<endl;
	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);
	//cout << lca[2][0] << ' ' << dp[2][0] << ' ' << ve[3] << endl;
	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);
			//cout << i << ' ' << j << ' ' << Q << endl;
			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];
	vll acc(n+2);
	for (int i=1; i<=n; ++i) acc[i] = acc[i-1] + pre[i];

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

	ll current = ans;
	for (int i=2; i<=n; ++i){
		//ll delta = current - factor * ;
	}
	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){
      |                ~^~~~~~~~~~~~
deblo.cpp: In function 'void subeasy()':
deblo.cpp:111:5: warning: unused variable 'current' [-Wunused-variable]
  111 |  ll current = ans;
      |     ^~~~~~~

Subtask #1

45.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	3 ms	2668 KB	Output is correct
3	Correct	3 ms	2796 KB	Output is correct
4	Correct	37 ms	3052 KB	Output is correct
5	Correct	38 ms	2924 KB	Output is correct
6	Incorrect	53 ms	10216 KB	Output isn't correct
7	Incorrect	41 ms	9960 KB	Output isn't correct
8	Incorrect	55 ms	10088 KB	Output isn't correct
9	Incorrect	44 ms	10088 KB	Output isn't correct
10	Incorrect	54 ms	10088 KB	Output isn't correct