oj.uz

Submission #152379

# Submission time Handle Problem Language Result Execution time Memory
152379 2019-09-07T20:22:58 Z Breno_XD Poklon (COCI17_poklon7) C++14
96 / 120
 1000 ms 20376 KB 
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second

const int MAXN = 1000010;
int n, aans, bans;
int nivel[MAXN];
queue<pair<int,int> > fila;

struct nodes{

	int l,r;

};

nodes node[MAXN];

void dfs(int f, int p){

	// cout << "Demonstracao: " << f << "    " << p << endl;

	nivel[f] = nivel[p] + 1;

	if(node[f].r < 0) fila.push(make_pair(abs(node[f].r) , nivel[f]+1));		
	else dfs(node[f].r, f);

	if(node[f].l < 0) fila.push(make_pair(abs(node[f].l) , nivel[f]+1));
	else dfs(node[f].l, f);

}


int main(){

	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin >> n;

	for(int i=1; i<=n; i++) cin >> node[i].l >> node[i].r;

	nivel[0] = -1;
	dfs(1,0);

	while(!fila.empty()){

		pair<int,int> atual = fila.front();
		fila.pop();

		//Vamos compara ans e atual.x

		// cout << "Atual: " << atual.x << "   " << atual.y << endl;
		// cout << "Ans:   " << aans << "   " << bans << endl; 

		//Primeiro verificamos o último bit
		int tam = 32-__builtin_clz(atual.x) + atual.y;
		int tamans = 32-__builtin_clz(aans) + bans;

		if(tamans != tam){

			if(tamans < tam){

				// cout << "Atualizei tamdiff\n";
				aans = atual.x;
				bans = atual.y;

			}

		}else{

			tam = 31-__builtin_clz(atual.x);
			tamans = 31-__builtin_clz(aans);

			int size = min(tam, tamans);

			for(int i=size; i>=0; i--){

				// cout << "i: " << i << endl;
				// cout << "Tam: " << tam << "    tamans: " << tamans << endl; 

				bool ok = (atual.x&(1<<tam));
				bool okans = (aans&(1<<tamans));

				if(ok && !okans){
					//cout << "Atualizei tamiguais\n";
					aans = atual.x;
					bans = atual.y;
					break;
				}
				if(!ok && okans) break;

				tam--;
				tamans--;

			}

		}

	}

	bool verifica = false;
	for(int i=30; i>=0; i--){

		if((aans&(1<<i))) verifica = true;

		if(!verifica) continue;

		bool bit = (aans&(1<<i));

		cout << bit;

	}

	for(int i=1; i<=bans; i++){

		cout << 0;

	}

	cout << "\n";

}

Subtask #1
96.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 15 ms 968 KB Output is correct
12 Correct 19 ms 888 KB Output is correct
13 Correct 71 ms 3368 KB Output is correct
14 Correct 138 ms 6392 KB Output is correct
15 Correct 134 ms 4088 KB Output is correct
16 Correct 477 ms 18880 KB Output is correct
17 Execution timed out 1065 ms 20212 KB Time limit exceeded
18 Execution timed out 1060 ms 19548 KB Time limit exceeded
19 Execution timed out 1064 ms 20376 KB Time limit exceeded
20 Execution timed out 1075 ms 20024 KB Time limit exceeded