Submission #152403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152403	2019-09-07T21:55:15 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	120 / 120	935 ms	249756 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[1000010];
vector < bool >resp;

void dfs(int u, int niv)
{
	if(u > n or !(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++)
	{
		dfs(grafo[u][i], 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

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	23800 KB	Output is correct
2	Correct	23 ms	23800 KB	Output is correct
3	Correct	23 ms	23848 KB	Output is correct
4	Correct	24 ms	23800 KB	Output is correct
5	Correct	23 ms	23800 KB	Output is correct
6	Correct	24 ms	23800 KB	Output is correct
7	Correct	23 ms	23800 KB	Output is correct
8	Correct	24 ms	23800 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	32 ms	25080 KB	Output is correct
12	Correct	34 ms	24908 KB	Output is correct
13	Correct	68 ms	30332 KB	Output is correct
14	Correct	112 ms	37240 KB	Output is correct
15	Correct	104 ms	27384 KB	Output is correct
16	Correct	315 ms	59256 KB	Output is correct
17	Correct	707 ms	100088 KB	Output is correct
18	Correct	726 ms	108696 KB	Output is correct
19	Correct	848 ms	92408 KB	Output is correct
20	Correct	935 ms	249756 KB	Output is correct