Submission #42384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42384	2018-02-26T15:32:36 Z	wasyl	Poklon (COCI17_poklon7)	C++11	108 / 120	1000 ms	99952 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	252 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	472 KB	Output is correct
4	Correct	1 ms	472 KB	Output is correct
5	Correct	1 ms	472 KB	Output is correct
6	Correct	1 ms	472 KB	Output is correct
7	Correct	2 ms	472 KB	Output is correct
8	Correct	2 ms	580 KB	Output is correct
9	Correct	2 ms	628 KB	Output is correct
10	Correct	3 ms	628 KB	Output is correct
11	Correct	13 ms	1828 KB	Output is correct
12	Correct	19 ms	1956 KB	Output is correct
13	Correct	74 ms	7208 KB	Output is correct
14	Correct	139 ms	14004 KB	Output is correct
15	Correct	133 ms	14004 KB	Output is correct
16	Correct	432 ms	42460 KB	Output is correct
17	Correct	973 ms	95752 KB	Output is correct
18	Correct	985 ms	99952 KB	Output is correct
19	Execution timed out	1080 ms	99952 KB	Time limit exceeded
20	Execution timed out	1086 ms	99952 KB	Time limit exceeded