Submission #894955

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894955	2023-12-29T09:46:42 Z	therealpain	Deblo (COCI18_deblo)	C++17	45 / 90	1000 ms	13908 KB

deblo

#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;

int n;
int a[N];
vector <int> adj[N];

namespace subtask1 {
	int d[1005];

	void dfs(int u, int p) {
		for (int v : adj[u]) {
			if (v == p) continue;
			d[v] = (d[u] ^ a[v]);
			dfs(v, u);
		}
	}


	void solve() {
		long long ans = 0;

		for (int i = 1; i <= n; ++i) {
			memset(d, 0, sizeof d);
			d[i] = a[i];
			dfs(i, i);
			for (int j = i; j <= n; ++j) {
				ans = ans + d[j];
				//cout << i << ' ' << j << ' ' << d[j] << '\n';
			}
		}

		cout << ans;
	}
};

namespace subtask3 {
	const int LOG = 19;
	int pref[N];
	long long ans;

	void solve() {
		for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] ^ a[i];
		//for (int i = 1; i <= n; ++i) cout << pref[i] << " \n"[i == n];
		for (int i = 1; i <= n; ++i) {
			for (int j = i; j <= n; ++j) {
				int lo = j, hi = n, res = j;
				while (lo <= hi) {
					int mid = lo + hi >> 1;
					if ((pref[j] ^ pref[i - 1]) == (pref[mid] ^ pref[i - 1])) {
						res = mid;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}

				ans += 1LL * (res - j + 1) * (pref[j] ^ pref[i - 1]);
				//cout << i << ' ' << j << ' ' << res << ' ' << (pref[j] ^ pref[i - 1]) << '\n';
				j = res;
			}
		}

		cout << ans;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	if (n <= 1000) subtask1::solve();
	else subtask3::solve();
}

Compilation message

deblo.cpp: In function 'void subtask3::solve()':
deblo.cpp:67:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |      int mid = lo + hi >> 1;
      |                ~~~^~~~

Subtask #1

45.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8540 KB	Output is correct
2	Correct	2 ms	8632 KB	Output is correct
3	Correct	2 ms	8540 KB	Output is correct
4	Correct	8 ms	8540 KB	Output is correct
5	Correct	8 ms	8724 KB	Output is correct
6	Execution timed out	1087 ms	13848 KB	Time limit exceeded
7	Execution timed out	1062 ms	13908 KB	Time limit exceeded
8	Execution timed out	1022 ms	13904 KB	Time limit exceeded
9	Execution timed out	1030 ms	13904 KB	Time limit exceeded
10	Execution timed out	1056 ms	13908 KB	Time limit exceeded