oj.uz

Submission #87707

# Submission time Handle Problem Language Result Execution time Memory
87707 2018-12-02T06:11:35 Z win11905 Deblo (COCI18_deblo) C++11
90 / 90
 403 ms 16944 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

const int N = 1e5+5;

class deblo {
private:
	int n, A[N], dp[N];
	long ans;
	bool check[N];
	vector<int> g[N];
	void find(int u, int p, int sz, pii &ret) {
		dp[u] = 1;
		int mx = 0;
		for(int v : g[u]) if(v != p and !check[v]) {
			find(v, u, sz, ret);
			dp[u] += dp[v], mx = max(mx, dp[v]);
		}
		mx = max(mx, sz - dp[u]);
		if(mx < ret.x) ret = pii(mx, u);
	}
	int step[2][22];
	void upd(int val) {
		for(int i = 21; ~i; --i) step[val >> i & 1][i]++;
	}
	long get(int val) {
		long sum = 0;
		for(int i = 21; ~i; --i) sum += (1ll << i) * step[(val >> i & 1) ^ 1][i];
		return sum;
	}
	void dfs(int u, int p, int d, bool st) {
		if(st) ans += get(d);
		else upd(d);
		for(int v : g[u]) if(v != p and !check[v]) dfs(v, u, d ^ A[v], st);
	}
	void solve(int u, int sz) {
	    memset(step, 0, sizeof step);
		pii ret(sz, -1);
		find(u, 0, sz, ret);
		check[u = ret.y] = true;
		upd(A[u]);
		for(int v : g[u]) if(!check[v]) {
			dfs(v, u, A[v], true);
			dfs(v, u, A[u] ^ A[v], false);
		}
		for(int v : g[u]) if(!check[v]) solve(v, dp[v] > dp[u] ? sz - dp[u] : dp[v]);
	}
public:
	void solve(istream& cin, ostream& cout) {
		cin >> n;
		for(int i = 1; i <= n; ++i) cin >> A[i], ans += A[i];
		for(int i = 1, u, v; i < n; ++i) {
			cin >> u >> v;
			g[u].emplace_back(v), g[v].emplace_back(u);
		}
		solve(1, n);
		cout << ans << endl;
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
		deblo *obj = new deblo();
		obj->solve(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 5 ms 3576 KB Output is correct
3 Correct 6 ms 3656 KB Output is correct
4 Correct 7 ms 3788 KB Output is correct
5 Correct 6 ms 3848 KB Output is correct
6 Correct 274 ms 15108 KB Output is correct
7 Correct 271 ms 16944 KB Output is correct
8 Correct 296 ms 16944 KB Output is correct
9 Correct 283 ms 16944 KB Output is correct
10 Correct 403 ms 16944 KB Output is correct