답안 #89345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89345 2018-12-12T00:21:50 Z jasony123123 Poklon (COCI17_poklon7) C++11
120 / 120
305 ms 40108 KB
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }
inline void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */
#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}
/**************************COCI 2016-2017 R7 P4*************************/

int __builtin_clz(int x) { // #0s at beginning
	RFORE(i, 31, 0)
		if (((1 << i)&x) != 0) {
			return 31 - i;
		}
	return 32;
}

struct BitNum{
	int num, bits;
	int len;
	BitNum(int x, int b) {
		num = x, bits = b;
		len = 32 - __builtin_clz(x);
	}
	int totalLen() const {
		return bits + len;
	}
	int top32() const {
		return num << (32 - len);
	}
	bool operator<(BitNum const &other) const {
		if (totalLen() < other.totalLen()) return 1;
		else if (totalLen() > other.totalLen()) return 0;
		else return top32() < other.top32();
	}
	string toString() {
		string ret = "";

		RFORE(i, len - 1, 0)
			ret += ((num&(1 << i)) > 0 ? '1' : '0');
		FOR(i, 0, bits)
			ret += '0';
		return ret;
	}
};

int N, C[1000000][2];
BitNum maxb(0, 0);

void dfs(int x, int dep) {
	if (x < 0) {
		maxx(maxb, BitNum(-x, dep));
		return;
	}
	dfs(C[x][0], dep + 1), dfs(C[x][1], dep + 1);
}

int main() {
	io();
	cin >> N;
	FORE(i, 1, N) cin >> C[i][0] >> C[i][1];
	dfs(1, 0);
	cout << maxb.toString() << "\n";
	return 0;
}

Compilation message

poklon.cpp: In function 'int __builtin_clz(int)':
poklon.cpp:38:5: warning: new declaration 'int __builtin_clz(int)' ambiguates built-in declaration 'int __builtin_clz(unsigned int)' [-Wbuiltin-declaration-mismatch]
 int __builtin_clz(int x) { // #0s at beginning
     ^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 2 ms 664 KB Output is correct
9 Correct 2 ms 664 KB Output is correct
10 Correct 2 ms 664 KB Output is correct
11 Correct 5 ms 748 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 17 ms 1608 KB Output is correct
14 Correct 30 ms 2572 KB Output is correct
15 Correct 31 ms 2572 KB Output is correct
16 Correct 103 ms 5776 KB Output is correct
17 Correct 236 ms 11984 KB Output is correct
18 Correct 239 ms 13016 KB Output is correct
19 Correct 295 ms 13016 KB Output is correct
20 Correct 305 ms 40108 KB Output is correct