oj.uz

답안 #89346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89346 2018-12-12T00:22:34 Z jasony123123 Poklon (COCI17_poklon7) C++11
120 / 120
 286 ms 40088 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;
}

Subtask #1
120.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 18 ms 1404 KB Output is correct
14 Correct 30 ms 2416 KB Output is correct
15 Correct 30 ms 2416 KB Output is correct
16 Correct 101 ms 5916 KB Output is correct
17 Correct 231 ms 12108 KB Output is correct
18 Correct 233 ms 12976 KB Output is correct
19 Correct 286 ms 12976 KB Output is correct
20 Correct 285 ms 40088 KB Output is correct