Submission #152387

#	Time	Username	Problem	Language	Result	Execution time	Memory
152387		sofhiasouza	Poklon (COCI17_poklon7)	C++14	108 / 120	1100 ms	201272 KiB

poklon

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

const int maxn = 3e6+10;

int n, cont, qtdz, val[maxn];

vector < int > grafo[maxn], resp;

void comp(vector < int > aux, int niv)
{
	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;
		}
	}
}

void dfs(int u, int niv)
{
	if(!grafo[u].size())
	{
		vector < int > 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 comp(std::vector<int>, int)':
poklon.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < aux.size() ; i++) resp.pb(aux[i]);
                   ~~^~~~~~~~~~~~
poklon.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < aux.size() and i < resp.size() ; i++)
                   ~~^~~~~~~~~~~~
poklon.cpp:21:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < aux.size() and i < resp.size() ; i++)
                                      ~~^~~~~~~~~~~~~
poklon.cpp:28: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:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < aux.size() ; j++) resp.pb(aux[j]);
                    ~~^~~~~~~~~~~~
poklon.cpp: In function 'void dfs(int, int)':
poklon.cpp:63: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:67: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:67: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:74: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:82: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:89: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:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < resp.size() ; i++) cout << resp[i];
                  ~~^~~~~~~~~~~~~

• Subtask 1: 108 / 120