Submission #89346

#	Time	Username	Problem	Language	Result	Execution time	Memory
89346		jasony123123	Poklon (COCI17_poklon7)	C++11	120 / 120	286 ms	40088 KiB

poklon

#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 / 120