Submission #152393

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152393	2019-09-07T21:11:24 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	114 / 120	922 ms	262148 KB

poklon

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

const int maxn = 4e6+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);
	}
}

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	88 ms	94200 KB	Output is correct
2	Correct	88 ms	94200 KB	Output is correct
3	Correct	95 ms	94260 KB	Output is correct
4	Correct	88 ms	94300 KB	Output is correct
5	Correct	89 ms	94328 KB	Output is correct
6	Correct	89 ms	94216 KB	Output is correct
7	Correct	88 ms	94328 KB	Output is correct
8	Correct	88 ms	94456 KB	Output is correct
9	Correct	88 ms	94332 KB	Output is correct
10	Correct	89 ms	94428 KB	Output is correct
11	Correct	113 ms	95608 KB	Output is correct
12	Correct	122 ms	95392 KB	Output is correct
13	Correct	148 ms	100728 KB	Output is correct
14	Correct	192 ms	107256 KB	Output is correct
15	Correct	172 ms	98268 KB	Output is correct
16	Correct	381 ms	129104 KB	Output is correct
17	Correct	768 ms	169776 KB	Output is correct
18	Correct	795 ms	177720 KB	Output is correct
19	Correct	922 ms	163980 KB	Output is correct
20	Runtime error	583 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)