Submission #541648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
541648	2022-03-24T00:44:14 Z	colazcy	Poklon (COCI17_poklon7)	C++17	120 / 120	116 ms	73608 KB

poklon

#include <cstdio>
#include <cassert>
#include <cctype>
#include <algorithm>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 1e6 + 10;
using ll = long long;
using i128 = __int128_t;
int read(){
	int x = 0,f = 1; char c = std::getchar();
	while(!std::isdigit(c))f = c == '-' ? -1 : 1,c = std::getchar();
	while(std::isdigit(c))x = x * 10 + c - '0',c = std::getchar();
	return x * f;
}
template <typename T>
void wirte_bin(T x){
	char buf[233];
	int top = 0;
	do{
		buf[++top] = '0' + x % 2;
		x /= 2;
	}while(x);
	per(i,top,1)std::putchar(buf[i]);
}
struct Integer{
	ll v;
	int d;
	bool operator < (const Integer &rhs)const{
		if(std::abs(d - rhs.d) >= 64)return d < rhs.d;
		let v1 = i128(v) << (d - std::min(d,rhs.d));
		let v2 = i128(rhs.v) << (rhs.d - std::min(d,rhs.d));
		return v1 < v2;
	}	
}ans;
int n,ls[maxn],rs[maxn];
ll solve(const int x,const int dep = 0){
	if(x < 0){
		ans = std::max(ans,Integer{-x,dep});
		return -x;
	}
	ll res = 0;
	res += solve(ls[x],dep + 1);
	res += solve(rs[x],dep + 1);
	ans = std::max(ans,Integer{res,dep});
	return res;
}
int main(){
	// std::freopen("poklon.in","r",stdin);
	// std::freopen("poklon.out","w",stdout);
	n = read();
	rep(i,1,n)
		ls[i] = read(),rs[i] = read();
	solve(1);
	wirte_bin(ans.v);
	repn(ans.d)std::putchar('0');
	std::puts("");
	// std::fclose(stdin);
	// std::fclose(stdout);
	return 0;
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	296 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	308 KB	Output is correct
11	Correct	2 ms	724 KB	Output is correct
12	Correct	2 ms	724 KB	Output is correct
13	Correct	6 ms	2644 KB	Output is correct
14	Correct	13 ms	5144 KB	Output is correct
15	Correct	14 ms	2648 KB	Output is correct
16	Correct	42 ms	14576 KB	Output is correct
17	Correct	99 ms	32464 KB	Output is correct
18	Correct	99 ms	34716 KB	Output is correct
19	Correct	113 ms	33828 KB	Output is correct
20	Correct	116 ms	73608 KB	Output is correct