Submission #85959

#	Time	Username	Problem	Language	Result	Execution time	Memory
85959		tmwilliamlin168	ČVENK (COI15_cvenk)	C++14	0 / 100	423 ms	525312 KiB

cvenk

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5, mxM=261*mxN;
int n, m, ri, ci;
ll s1[mxM], s2[mxM];
vector<array<int, 2>> ps, adj[mxM];

void ae(int u, int v, int w) {
	adj[u].push_back({v, w});
	adj[v].push_back({u, w});
}

array<int, 3> bld(vector<array<int, 2>> &ps, int k=30) {
	if(!k) {
		s1[m++]+=ps.size();
		return {m-1, m-1, m-1};
	}
	if(!ps.size()) {
		m+=3;
		ae(m-3, m-2, (1<<k)-1);
		ae(m-3, m-1, (1<<k)-1);
		return {m-3, m-2, m-1};
	}
	vector<array<int, 2>> np[3];
	for(array<int, 2> a : ps)
		np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);
	array<int, 3> c[3];
	for(int i=0; i<3; ++i)
		c[i]=bld(np[i], k-1);
	ae(c[0][1], c[1][0], 1);
	ae(c[0][2], c[2][0], 1);
	return {c[0][0], c[1][1], c[2][2]};
}

void dfs1(int u=0, int p=-1) {
	for(array<int, 2> v : adj[u]) {
		if(v[0]==p)
			continue;
		dfs1(v[0], u);
		s1[u]+=s1[v[0]];
		s2[u]+=s2[v[0]]+s1[v[0]]*v[1];
	}
}

ll dfs2(int u=0, int p=-1, ll s2p=s2[0]) {
	for(array<int, 2> v : adj[u])
		if(v[0]!=p&&s1[v[0]]*2>n)
			return dfs2(v[0], u, s2p+(n-2*s1[v[0]])*v[1]);
	cout << s2p;
	exit(0);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> ri >> ci;
		ps.push_back({ri, ci});
	}
	bld(ps);
	dfs1();
	dfs2();
}

Compilation message (stderr)

cvenk.cpp: In function 'std::array<int, 3> bld(std::vector<std::array<int, 2> >&, int)':
cvenk.cpp:29:13: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);
            ~^~
cvenk.cpp:29:26: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);
                         ~^~
cvenk.cpp:29:15: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40