oj.uz

Submission #152387

# Submission time Handle Problem Language Result Execution time Memory
152387 2019-09-07T20:51:58 Z sofhiasouza Poklon (COCI17_poklon7) C++14
108 / 120
 1000 ms 201272 KB 
#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

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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 70776 KB Output is correct
2 Correct 68 ms 70800 KB Output is correct
3 Correct 68 ms 70904 KB Output is correct
4 Correct 67 ms 70776 KB Output is correct
5 Correct 67 ms 70776 KB Output is correct
6 Correct 68 ms 70776 KB Output is correct
7 Correct 68 ms 70776 KB Output is correct
8 Correct 68 ms 70776 KB Output is correct
9 Correct 68 ms 70776 KB Output is correct
10 Correct 69 ms 70776 KB Output is correct
11 Correct 78 ms 71800 KB Output is correct
12 Correct 81 ms 71772 KB Output is correct
13 Correct 125 ms 75336 KB Output is correct
14 Correct 180 ms 79744 KB Output is correct
15 Correct 203 ms 74744 KB Output is correct
16 Correct 453 ms 95496 KB Output is correct
17 Correct 964 ms 124144 KB Output is correct
18 Correct 974 ms 129052 KB Output is correct
19 Execution timed out 1094 ms 124280 KB Time limit exceeded
20 Execution timed out 1100 ms 201272 KB Time limit exceeded