Submission #152390

#	Time	Username	Problem	Language	Result	Execution time	Memory
152390		sofhiasouza	Poklon (COCI17_poklon7)	C++14	114 / 120	930 ms	262148 KiB

poklon

#include <bits/stdc++.h>
#define pb push_back
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);
	}
}

int 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 (stderr)

poklon.cpp: In function 'void dfs(int, int)':
poklon.cpp:33: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:37: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:37: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:44: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:52: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:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[u].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
poklon.cpp: In function 'int main()':
poklon.cpp:99: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 / 120