oj.uz

답안 #152393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152393 2019-09-07T21:11:24 Z sofhiasouza Poklon (COCI17_poklon7) C++14
114 / 120
 922 ms 262148 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int long long
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(!(int)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((int)aux.size()+niv > (int)resp.size()+qtdz)
		{
			resp.clear();
			qtdz = niv;
			for(int i = 0 ; i < (int)aux.size() ; i++) resp.pb(aux[i]);
		}
		else if((int)aux.size()+niv == (int)resp.size()+qtdz)
		{
			for(int i = 0 ; i < (int)aux.size() and i < (int)resp.size() ; i++)
			{
				if(resp[i] > aux[i]) return;
				else if(resp[i] < aux[i])
				{
					resp.clear();
					qtdz = niv;
					for(int j = 0 ; j < (int)aux.size() ; j++) resp.pb(aux[j]);
					return;
				}
			}
			if((int)aux.size() > (int)resp.size())
			{
				resp.clear();
				qtdz = niv;
				for(int j = 0 ; j < (int)aux.size() ; j++) resp.pb(aux[j]);
				return;
			}
		}

		return;
	}
	for(int i = 0 ; i < (int)grafo[u].size() ; i++)
	{
		int v = grafo[u][i];
		dfs(v, niv+1);
	}
}

int32_t 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 < (int)resp.size() ; i++) cout << resp[i];
	for(int i = 0 ; i < qtdz ; i++) cout << 0;
	cout << "\n";
}

Subtask #1
114.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 94200 KB Output is correct
2 Correct 88 ms 94200 KB Output is correct
3 Correct 95 ms 94260 KB Output is correct
4 Correct 88 ms 94300 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 89 ms 94216 KB Output is correct
7 Correct 88 ms 94328 KB Output is correct
8 Correct 88 ms 94456 KB Output is correct
9 Correct 88 ms 94332 KB Output is correct
10 Correct 89 ms 94428 KB Output is correct
11 Correct 113 ms 95608 KB Output is correct
12 Correct 122 ms 95392 KB Output is correct
13 Correct 148 ms 100728 KB Output is correct
14 Correct 192 ms 107256 KB Output is correct
15 Correct 172 ms 98268 KB Output is correct
16 Correct 381 ms 129104 KB Output is correct
17 Correct 768 ms 169776 KB Output is correct
18 Correct 795 ms 177720 KB Output is correct
19 Correct 922 ms 163980 KB Output is correct
20 Runtime error 583 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)