oj.uz

답안 #85963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85963 2018-11-23T12:10:52 Z tmwilliamlin168 ČVENK (COI15_cvenk) C++14
0 / 100
 422 ms 525312 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=1e5, mxM=261*mxN;
int n, m, ri, ci, s1[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]};
}

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

void dfs2(ll s2, int u=0, int p=-1) {
	for(array<int, 2> v : adj[u])
		if(v[0]!=p&&s1[v[0]]*2>n)
			dfs2(s2+(ll)(n-2*s1[v[0]])*v[1], v[0], u);
	cout << s2;
	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);
	dfs2(dfs1());
}

Compilation message

cvenk.cpp: In function 'std::array<int, 3> bld(std::vector<std::array<int, 2> >&, int)':
cvenk.cpp:28:13: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);
            ~^~
cvenk.cpp:28:26: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   np[a[0]>>k-1&1|(a[1]>>k-1&1)<<1].push_back(a);
                         ~^~
cvenk.cpp:28: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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 422 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 421 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 419 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 372 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -