Submission #152402

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152402	2019-09-07T21:49:10 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	114 / 120	891 ms	262148 KB

poklon

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

const int maxn = 2e6+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	45 ms	47352 KB	Output is correct
2	Correct	45 ms	47352 KB	Output is correct
3	Correct	45 ms	47352 KB	Output is correct
4	Correct	44 ms	47352 KB	Output is correct
5	Correct	45 ms	47324 KB	Output is correct
6	Correct	44 ms	47352 KB	Output is correct
7	Correct	44 ms	47324 KB	Output is correct
8	Correct	45 ms	47352 KB	Output is correct
9	Correct	45 ms	47352 KB	Output is correct
10	Correct	45 ms	47352 KB	Output is correct
11	Correct	53 ms	48632 KB	Output is correct
12	Correct	56 ms	48376 KB	Output is correct
13	Correct	90 ms	53880 KB	Output is correct
14	Correct	134 ms	60824 KB	Output is correct
15	Correct	130 ms	50952 KB	Output is correct
16	Correct	342 ms	82824 KB	Output is correct
17	Correct	733 ms	123768 KB	Output is correct
18	Correct	770 ms	132344 KB	Output is correct
19	Correct	891 ms	117992 KB	Output is correct
20	Runtime error	593 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)