답안 #87707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87707	2018-12-02T06:11:35 Z	win11905	Deblo (COCI18_deblo)	C++11	90 / 90	403 ms	16944 KB

deblo

/**
 * 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

#	결과	실행 시간	메모리	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