Submission #152401

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152401	2019-09-07T21:48:45 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	96 / 120	319 ms	64376 KB

poklon

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

const int maxn = 1e6+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

96.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	23800 KB	Output is correct
4	Correct	23 ms	23800 KB	Output is correct
5	Correct	23 ms	23800 KB	Output is correct
6	Correct	23 ms	23928 KB	Output is correct
7	Correct	23 ms	23880 KB	Output is correct
8	Correct	23 ms	23800 KB	Output is correct
9	Correct	23 ms	23900 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	32 ms	25208 KB	Output is correct
12	Correct	34 ms	25068 KB	Output is correct
13	Correct	69 ms	31068 KB	Output is correct
14	Correct	113 ms	38504 KB	Output is correct
15	Correct	108 ms	28792 KB	Output is correct
16	Correct	319 ms	61176 KB	Output is correct
17	Runtime error	146 ms	64376 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	144 ms	63868 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	54 ms	48248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	54 ms	47992 KB	Execution killed with signal 11 (could be triggered by violating memory limits)