Submission #152386

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152386	2019-09-07T20:50:05 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	96 / 120	1000 ms	219392 KB

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);
		}

		comp(aux, niv);

		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: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:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < resp.size() ; i++) cout << resp[i];
                  ~~^~~~~~~~~~~~~

Subtask #1

96.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	70776 KB	Output is correct
2	Correct	68 ms	70776 KB	Output is correct
3	Correct	67 ms	70752 KB	Output is correct
4	Correct	66 ms	70816 KB	Output is correct
5	Correct	66 ms	70776 KB	Output is correct
6	Correct	76 ms	70892 KB	Output is correct
7	Correct	68 ms	70776 KB	Output is correct
8	Correct	73 ms	70740 KB	Output is correct
9	Correct	72 ms	70868 KB	Output is correct
10	Correct	69 ms	70836 KB	Output is correct
11	Correct	78 ms	71708 KB	Output is correct
12	Correct	82 ms	71544 KB	Output is correct
13	Correct	125 ms	75464 KB	Output is correct
14	Correct	185 ms	80144 KB	Output is correct
15	Correct	185 ms	74360 KB	Output is correct
16	Correct	475 ms	96632 KB	Output is correct
17	Execution timed out	1004 ms	127384 KB	Time limit exceeded
18	Execution timed out	1014 ms	133112 KB	Time limit exceeded
19	Execution timed out	1079 ms	129024 KB	Time limit exceeded
20	Execution timed out	1091 ms	219392 KB	Time limit exceeded