Submission #363436

# Submission time Handle Problem Language Result Execution time Memory
363436 2021-02-06T02:08:20 Z idontreallyknow Poklon (COCI17_poklon7) C++14
12 / 120
413 ms 123996 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937/*_64*/ rng(chrono::steady_clock::now().time_since_epoch().count());
#define printArr(arr, n) cerr << #arr << " = ["; for(int i=0; i<(n); i++){if (i) cerr << ", "; cerr << arr[i];} cerr << "]\n"
template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";};
template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";};
void _print() {cerr << "]\n";}
template <class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define fi first
#define se second
#define SZ(x) (int)((x).size())
#define pii pair<int,int>
const int mx = 1e6+50;
ll a[mx], b[mx], depth[mx];
vector<pii> stuff;
void dfs(int v)
{
	if (a[v] <= 0) {
		stuff.emplace_back(-a[v],depth[v]+1);
	} else {
		depth[a[v]] = depth[v]+1;
		dfs(a[v]);
	}
	if (b[v] <= 0) {
		stuff.emplace_back(-b[v],depth[v]+1);
	} else {
		depth[b[v]] = depth[v]+1;
		dfs(b[v]);
	}
}
const ll inf = (1<<31);
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int q = 1; q <= n; q++) cin >> a[q] >> b[q];
	dfs(1);
	vector<pii> things;
	for (pii e : stuff) {
		if (e.fi == 0) {
			things.emplace_back(-1,0);
			continue;
		}
		int msb = 31 - __builtin_clz(e.fi);
		ll x = e.fi;
		if (msb+e.se >= 31) {
			while (x < inf) x *= 2;
		} else {
			int msb1 = e.se;
			while (msb1 > 0) {
				msb1--;
				x *= 2;
			}
		}
		things.emplace_back(msb+e.se,x);
	}
	sort(things.begin(), things.end());
	ll x,y;
	tie(x,y) = things.back();
	if (x == -1) {
		cout << "0\n";
		return 0;
	}
	if (x < 31) {
		for (int q = x; q >= 0; q--) {
			cout << (((1LL<<q)&y) > 0 ? 1 : 0);
		}
		cout << "\n";
	} else {
		for (int q = 31; q >= 0; q--) {
			cout << (((1LL<<q)&y) > 0 ? 1 : 0);
			x--;
		}
		while (x > 0) {
			cout << 0;
			x--;
		}
		cout << "\n";
	}
	return 0;
}

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 1 ms 364 KB Output isn't correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Incorrect 1 ms 364 KB Output isn't correct
11 Incorrect 4 ms 1308 KB Output isn't correct
12 Incorrect 5 ms 1388 KB Output isn't correct
13 Incorrect 20 ms 5100 KB Output isn't correct
14 Incorrect 43 ms 9964 KB Output isn't correct
15 Incorrect 40 ms 6632 KB Output isn't correct
16 Incorrect 137 ms 30804 KB Output isn't correct
17 Incorrect 342 ms 67328 KB Output isn't correct
18 Incorrect 347 ms 70488 KB Output isn't correct
19 Incorrect 413 ms 72408 KB Output isn't correct
20 Incorrect 380 ms 123996 KB Output isn't correct