Submission #152400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152400	2019-09-07T21:34:59 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	114 / 120	908 ms	262148 KB

poklon

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int maxn = 3e6+10;

int n, cont, qtdz, val[maxn];

vector < int > grafo[maxn];
vector < bool >resp;

void dfs(int u, int niv)
{
	if(!(int)grafo[u].size())
	{
		vector < bool > aux;

		int flag = 0;
		for(int i = 31 ; i >= 0 ; i--)
		{
			if(val[u]&(1 << i))
			{
				flag = 1;
				aux.pb(1);
			}
			else if(flag) aux.pb(0);
		}

		if((int)aux.size()+niv > (int)resp.size()+qtdz)
		{
			resp.clear();
			qtdz = niv;
			for(int i = 0 ; i < (int)aux.size() ; i++) resp.pb(aux[i]);
		}
		else if((int)aux.size()+niv == (int)resp.size()+qtdz)
		{
			for(int i = 0 ; i < (int)aux.size() and i < (int)resp.size() ; i++)
			{
				if(resp[i] > aux[i]) return;
				else if(resp[i] < aux[i])
				{
					resp.clear();
					qtdz = niv;
					for(int j = 0 ; j < (int)aux.size() ; j++) resp.pb(aux[j]);
					return;
				}
			}
			if((int)aux.size() > (int)resp.size())
			{
				resp.clear();
				qtdz = niv;
				for(int j = 0 ; j < (int)aux.size() ; j++) resp.pb(aux[j]);
				return;
			}
		}

		return;
	}
	for(int i = 0 ; i < (int)grafo[u].size() ; i++)
	{
		int v = grafo[u][i];
		dfs(v, niv+1);
	}
	grafo[u].clear();
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;

	cont = n;
	for(int i = 1 ; i <= n ; i++)
	{
		int a, b;
		cin >> a >> b;
	
		if(a < 0)
		{
			cont++;
			val[cont] = a*(-1);
			grafo[i].pb(cont);
		}
		else grafo[i].pb(a);

		if(b < 0)
		{
			cont++;
			val[cont] = b*(-1);
			grafo[i].pb(cont);
		}
		else grafo[i].pb(b);
	}

	dfs(1, 0);

	for(int i = 0 ; i < (int)resp.size() ; i++) cout << resp[i];
	for(int i = 0 ; i < qtdz ; i++) cout << 0;
	cout << "\n";
}

Subtask #1

114.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	67 ms	70776 KB	Output is correct
3	Correct	67 ms	70776 KB	Output is correct
4	Correct	80 ms	70752 KB	Output is correct
5	Correct	69 ms	70776 KB	Output is correct
6	Correct	68 ms	70904 KB	Output is correct
7	Correct	67 ms	70848 KB	Output is correct
8	Correct	67 ms	70904 KB	Output is correct
9	Correct	67 ms	70876 KB	Output is correct
10	Correct	68 ms	70776 KB	Output is correct
11	Correct	76 ms	72056 KB	Output is correct
12	Correct	77 ms	71928 KB	Output is correct
13	Correct	112 ms	77280 KB	Output is correct
14	Correct	156 ms	84268 KB	Output is correct
15	Correct	151 ms	74352 KB	Output is correct
16	Correct	377 ms	106344 KB	Output is correct
17	Correct	759 ms	147224 KB	Output is correct
18	Correct	765 ms	155628 KB	Output is correct
19	Correct	908 ms	139460 KB	Output is correct
20	Runtime error	578 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)