Submission #152392

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152392	2019-09-07T21:07:31 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	114 / 120	934 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(!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(aux.size()+niv > resp.size()+qtdz)
		{
			resp.clear();
			qtdz = niv;
			for(int i = 0 ; i < aux.size() ; i++) resp.pb(aux[i]);
		}
		else if(aux.size()+niv == resp.size()+qtdz)
		{
			for(int i = 0 ; i < aux.size() and i < resp.size() ; i++)
			{
				if(resp[i] > aux[i]) return;
				else if(resp[i] < aux[i])
				{
					resp.clear();
					qtdz = niv;
					for(int j = 0 ; j < aux.size() ; j++) resp.pb(aux[j]);
					return;
				}
			}
			if(aux.size() > resp.size())
			{
				resp.clear();
				qtdz = niv;
				for(int j = 0 ; j < aux.size() ; j++) resp.pb(aux[j]);
				return;
			}
		}

		return;
	}
	for(int i = 0 ; i < 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 < resp.size() ; i++) cout << resp[i];
	for(int i = 0 ; i < qtdz ; i++) cout << 0;
	cout << "\n";
}

Compilation message

poklon.cpp: In function 'void dfs(long long int, long long int)':
poklon.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < aux.size() ; i++) resp.pb(aux[i]);
                    ~~^~~~~~~~~~~~
poklon.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < aux.size() and i < resp.size() ; i++)
                    ~~^~~~~~~~~~~~
poklon.cpp:38:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0 ; i < aux.size() and i < resp.size() ; i++)
                                       ~~^~~~~~~~~~~~~
poklon.cpp:45:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0 ; j < aux.size() ; j++) resp.pb(aux[j]);
                      ~~^~~~~~~~~~~~
poklon.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0 ; j < aux.size() ; j++) resp.pb(aux[j]);
                     ~~^~~~~~~~~~~~
poklon.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[u].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
poklon.cpp: In function 'int32_t main()':
poklon.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < resp.size() ; i++) cout << resp[i];
                  ~~^~~~~~~~~~~~~

Subtask #1

114.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	94328 KB	Output is correct
2	Correct	88 ms	94228 KB	Output is correct
3	Correct	88 ms	94328 KB	Output is correct
4	Correct	89 ms	94328 KB	Output is correct
5	Correct	89 ms	94220 KB	Output is correct
6	Correct	89 ms	94300 KB	Output is correct
7	Correct	88 ms	94328 KB	Output is correct
8	Correct	90 ms	94292 KB	Output is correct
9	Correct	90 ms	94328 KB	Output is correct
10	Correct	89 ms	94328 KB	Output is correct
11	Correct	97 ms	95576 KB	Output is correct
12	Correct	99 ms	95480 KB	Output is correct
13	Correct	152 ms	100728 KB	Output is correct
14	Correct	198 ms	107356 KB	Output is correct
15	Correct	172 ms	98300 KB	Output is correct
16	Correct	379 ms	129336 KB	Output is correct
17	Correct	792 ms	169976 KB	Output is correct
18	Correct	834 ms	177704 KB	Output is correct
19	Correct	934 ms	164236 KB	Output is correct
20	Runtime error	572 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)