Submission #152385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152385	2019-09-07T20:48:11 Z	sofhiasouza	Poklon (COCI17_poklon7)	C++14	96 / 120	1000 ms	100736 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()
{
	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: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

96.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	70776 KB	Output is correct
2	Correct	67 ms	70776 KB	Output is correct
3	Correct	67 ms	70776 KB	Output is correct
4	Correct	80 ms	70780 KB	Output is correct
5	Correct	68 ms	70748 KB	Output is correct
6	Correct	67 ms	70776 KB	Output is correct
7	Correct	66 ms	70776 KB	Output is correct
8	Correct	73 ms	70748 KB	Output is correct
9	Correct	77 ms	70884 KB	Output is correct
10	Correct	69 ms	70792 KB	Output is correct
11	Correct	91 ms	71840 KB	Output is correct
12	Correct	94 ms	71840 KB	Output is correct
13	Correct	181 ms	76340 KB	Output is correct
14	Correct	289 ms	81716 KB	Output is correct
15	Correct	288 ms	75996 KB	Output is correct
16	Correct	824 ms	100736 KB	Output is correct
17	Execution timed out	1078 ms	97820 KB	Time limit exceeded
18	Execution timed out	1086 ms	98240 KB	Time limit exceeded
19	Execution timed out	1089 ms	98116 KB	Time limit exceeded
20	Execution timed out	1085 ms	98040 KB	Time limit exceeded