oj.uz

답안 #363445

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
363445 2021-02-06T02:44:05 Z idontreallyknow Poklon (COCI17_poklon7) C++14
120 / 120
 454 ms 111192 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 = (1LL<<33);
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<pair<ll,ll>> 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 >= 33) {
			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 < 33) {
		for (int q = x; q >= 0; q--) {
			cout << (((1LL<<q)&y) > 0 ? 1 : 0);
		}
		cout << "\n";
	} else {
		for (int q = 33; q >= 0; q--) {
			cout << ((((1LL<<q)&y) > 0) ? 1 : 0);
			x--;
		}
		while (x >= 0) {
			cout << 0;
			x--;
		}
		cout << "\n";
	}
	return 0;
}

Subtask #1
120.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 1388 KB Output is correct
12 Correct 5 ms 1408 KB Output is correct
13 Correct 21 ms 4592 KB Output is correct
14 Correct 41 ms 8940 KB Output is correct
15 Correct 40 ms 5740 KB Output is correct
16 Correct 145 ms 27108 KB Output is correct
17 Correct 365 ms 57832 KB Output is correct
18 Correct 374 ms 60756 KB Output is correct
19 Correct 454 ms 59480 KB Output is correct
20 Correct 406 ms 111192 KB Output is correct