Submission #87814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
87814	2018-12-02T16:49:33 Z	Koschei	Deblo (COCI18_deblo)	C++17	90 / 90	236 ms	45408 KB

deblo

#include <bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 1e5 + 7;
const int LOG = 23;

int n;
llint s;
bool visited[MAXN];
int v[MAXN];
int parent[MAXN];
llint dp[MAXN][LOG][2];
stack<int> leaves;
vector<int> graph[MAXN];

inline bool get(int i, llint b) 
{
	return ((1 << b) && ((1 << b) & v[i]));
}

void prep()
{
	stack<int> st;
	st.push(1);
	while (st.size())
	{
		int start = st.top();
		st.pop();
		int c = 0;
		visited[start] = 1;
		for (int next : graph[start])
		{
			if (!visited[next])
			{
				parent[next] = start;
				st.push(next);
				c++;
			}
		}
		if (!c) leaves.push(start);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> v[i];
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	prep();
	for (int i = 0; i < MAXN; i++) visited[i] = 0;
	while (leaves.size())
	{
		int vert = leaves.top();
		leaves.pop();
		visited[vert] = 1;
		for (llint b = 0; b < LOG; b++)
		{
			if (get(vert, b))
			{
				dp[vert][b][0] = 1;
				for (int v : graph[vert]) if (vert == parent[v])
				{
					dp[vert][b][0] += dp[v][b][1];
					dp[vert][b][1] += dp[v][b][0];
				}
			}
			else
			{
				dp[vert][b][1] = 1;
				for (int v : graph[vert]) if (vert == parent[v])
				{
					dp[vert][b][0] += dp[v][b][0];
					dp[vert][b][1] += dp[v][b][1];
				}	
			}
		}
		int par = parent[vert];
		if (par)
		{
			bool t = 1;
			for (int nex : graph[par]) if (par == parent[nex]) t &= visited[nex];
			if (t) leaves.push(par);
		}
	}
	for (int v = 1; v <= n; v++)
	{
		for (llint b = 0; b < LOG; b++)
		{
			llint clc0 = get(v, b);
			llint clc1 = !get(v, b);
			if (get(v, b)) s += (1 << b);
			for (int nx : graph[v]) 
			{
				if (v == parent[nx])
				{
				
					if (get(v, b)) 
					{
						s += (1 << b) * (dp[nx][b][0] * clc1);
						s += (1 << b) * (dp[nx][b][1] * clc0);
						clc1 += dp[nx][b][0];
						clc0 += dp[nx][b][1];
					}
					else
					{
						s += (1 << b) * (dp[nx][b][0] * clc1);
						s += (1 << b) * (dp[nx][b][1] * clc0);
						clc1 += dp[nx][b][1];
						clc0 += dp[nx][b][0];
					}
				}
			}
		}
	}
	cout << s;
	return 0;
}

Compilation message

deblo.cpp: In function 'bool get(int, llint)':
deblo.cpp:21:13: warning: '<<' in boolean context, did you mean '<' ? [-Wint-in-bool-context]
  return ((1 << b) && ((1 << b) & v[i]));
          ~~~^~~~~

Subtask #1

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2808 KB	Output is correct
2	Correct	5 ms	2808 KB	Output is correct
3	Correct	5 ms	3016 KB	Output is correct
4	Correct	7 ms	3480 KB	Output is correct
5	Correct	6 ms	3560 KB	Output is correct
6	Correct	137 ms	42992 KB	Output is correct
7	Correct	142 ms	43380 KB	Output is correct
8	Correct	156 ms	45184 KB	Output is correct
9	Correct	155 ms	45184 KB	Output is correct
10	Correct	236 ms	45408 KB	Output is correct