Submission #42384

#	Time	Username	Problem	Language	Result	Execution time	Memory
42384		wasyl	Poklon (COCI17_poklon7)	C++11	108 / 120	1086 ms	99952 KiB

poklon

#include <iostream>
#include <vector>
#include <algorithm>
#define d(...) __VA_ARGS__
#define EB(...) emplace_back(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template< typename t >
using V = vector< t >;

struct BinNum
{	
	string n;
	int ile_zer = 0;
	BinNum( ll v )
	{
		while ( v > 0 )
		{
			n += string( 1, ( v % 2 ) + '0' );
			v /= 2;
		}
		reverse( n.begin(), n.end() );
	}
	BinNum() : n( string() ) {}
	BinNum( const BinNum& a )
	{
		n = a.n;
		ile_zer = a.ile_zer;	
	}
	inline bool operator< ( BinNum&& a )  
	{
		if ( a.n.size() + a.ile_zer == (*this).n.size() + (*this).ile_zer )
		{
			if ( (*this).n.size() < a.n.size() )
			{
				(*this).ile_zer -= a.n.size() - (*this).n.size();
				(*this).n.resize( a.n.size(), '0' );
			}
			if ( a.n.size() < (*this).n.size() )
			{
				a.ile_zer -= (*this).n.size() - a.n.size();
				a.n.resize( (*this).n.size(), '0' );
			}
			for ( int i = 0; i < a.n.size(); ++i )
				if ( a.n[i] != (*this).n[i] )
					return (*this).n[i] < a.n[i];
			return false;
		}
		return (*this).n.size() + (*this).ile_zer < a.n.size() + a.ile_zer;
	}

	inline bool operator< ( BinNum& a )  
	{
		if ( a.n.size() + a.ile_zer == (*this).n.size() + (*this).ile_zer )
		{
			if ( (*this).n.size() < a.n.size() )
			{
				(*this).ile_zer -= a.n.size() - (*this).n.size();
				(*this).n.resize( a.n.size(), '0' );
			}
			if ( a.n.size() < (*this).n.size() )
			{
				a.ile_zer -= (*this).n.size() - a.n.size();
				a.n.resize( (*this).n.size(), '0' );
			}
			for ( int i = 0; i < a.n.size(); ++i )
				if ( a.n[i] != (*this).n[i] )
					return (*this).n[i] < a.n[i];
			return false;
		}
		return (*this).n.size() + (*this).ile_zer < a.n.size() + a.ile_zer;
	}
	
	inline void operator <<= ( int poz )
	{
		(*this).ile_zer += poz;
	} 
};

inline ostream& operator<< ( ostream& s, const BinNum& a )
{
	return s << a.n << string( a.ile_zer, '0' );
}

struct Node
{
	int l = -1, p = -1;
	BinNum sum;
};

int n;
V< Node > graf;

void dfs ( int v )
{
	for ( int s : { graf[v].l, graf[v].p } )
		if ( s != -1 )
		{
			dfs( s );
			if ( graf[v].sum < graf[s].sum )
				graf[v].sum = graf[s].sum;
		}
	graf[v].sum <<= 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	graf.resize( n + 1 );
	for ( int i = 1; i <= n; ++i )
	{
		int p, p2; cin >> p >> p2;
		if ( p < 0 )
		{
			if ( graf[i].sum < BinNum( -p ) )
				graf[i].sum = BinNum( -p );
		}
		else
			graf[i].l = p;
		if ( p2 < 0 )
		{
			if ( graf[i].sum < BinNum( -p2 ) )
				graf[i].sum = BinNum( -p2 );
		}
		else
			graf[i].p = p2;							
	}			
	dfs( 1 );
	cout << graf[1].sum << '\n';
}

Compilation message (stderr)

poklon.cpp: In member function 'bool BinNum::operator<(BinNum&&)':
poklon.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for ( int i = 0; i < a.n.size(); ++i )
                       ^
poklon.cpp: In member function 'bool BinNum::operator<(BinNum&)':
poklon.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for ( int i = 0; i < a.n.size(); ++i )
                       ^

• Subtask 1: 108 / 120