답안 #342088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342088	2021-01-01T10:57:23 Z	ruatin	Deblo (COCI18_deblo)	C++14	90 / 90	345 ms	15464 KB

deblo

#include <bits/stdc++.h>
using namespace std;
#define forinc(i, a, b) for(int i=a; i<=b; ++i)
#define fordec(i, a, b) for(int i=a; i>=b; --i)
#define forb(i, BS) for(int i=BS._Find_first(); i<BS.size(); i = BS._Find_next(i))
#define forv(a, b) for(auto &a:b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define bit(x,i) ((x>>i)&1)
#define onbit(x,i) (x|(1<<i))
#define offbit(x,i) (x&~(1<<i))
#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long lli;
typedef unsigned long long llu;
typedef pair<int, int> pii;
#define st first
#define nd second

const int N = 1e5 + 5, mod = 1e9+7;

int n, val[N];
vector<int> ke[N];

void readInput()
{
	cin >> n;
	forinc(i, 1, n) cin >> val[i];
	int u, v;
	forinc(i, 1, n-1)
	{
		cin >> u >> v;
		ke[u].pb(v);
		ke[v].pb(u);
	}
}

int dd[N], s[N], d[N];

void DFS(int u,int p)
{
	s[u] = 1;
	for(int v : ke[u]) if(v != p && !dd[v])
	{
        DFS(v, u);
        s[u] += s[v];
	}
}

int Find(int u,int p,int cnt)
{
    int vm = 0;
    for(int v:ke[u]) if(v!=p && !dd[v])
    {
        if(s[v] > s[vm]) vm = v;
    }
    if(s[vm] <= cnt/2) return u;
    else return Find(vm, u, cnt);
}

vector<int> tmp;
void get(int u, int p)
{
	tmp.pb(u);
	for(int v : ke[u]) if(v != p && !dd[v])
	{
		d[v] = (d[u] ^ val[v]);
		get(v, u);
	}
}

lli cnt[24], pre[24][2], lg = 22;

void centroid(int u)
{
	dd[u] = 1;
    DFS(u, 0);

    vector<int> child;
    memset(pre, 0, sizeof pre);

    forinc(b, 0, lg)
    {
    	if(bit(val[u], b)) cnt[b]++;
    	pre[b][bit(val[u], b)]++;
    }

    for(int v : ke[u]) if(!dd[v])
	{
        tmp.clear();
        d[v] = val[v]; get(v, u);

        for(int w : tmp)
		{
			forinc(b, 0, lg)
			{
				if(bit(d[w], b)) cnt[b] += pre[b][0];
				else cnt[b] += pre[b][1];
			}
		}

        for(int w : tmp)
		{
			int value = (d[w] ^ val[u]);
			forinc(b, 0, lg) pre[b][bit(value, b)]++;
		}

		child.pb(Find(v, u, s[v]));
	}
	for(int w : child) centroid(w);
}

int main()
{
    if(fopen("input.txt","r"))
    {
        freopen("input.txt","r",stdin);
//        freopen("output.txt","w",stdout);
    }
    fastio;

	readInput();

	memset(dd, 0, sizeof dd);
	DFS(1, 0);

	centroid(Find(1, 0, n));

	lli ans = 0;
	forinc(i, 0, lg) ans += (1ll << i) * cnt[i];
	cout << ans;
}

Compilation message

deblo.cpp: In function 'int main()':
deblo.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  117 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

90.0 / 90.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	3052 KB	Output is correct
2	Correct	2 ms	3052 KB	Output is correct
3	Correct	3 ms	3052 KB	Output is correct
4	Correct	4 ms	3180 KB	Output is correct
5	Correct	4 ms	3180 KB	Output is correct
6	Correct	345 ms	15464 KB	Output is correct
7	Correct	329 ms	15464 KB	Output is correct
8	Correct	326 ms	9200 KB	Output is correct
9	Correct	336 ms	8428 KB	Output is correct
10	Correct	316 ms	7916 KB	Output is correct