oj.uz

답안 #42384

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42384 2018-02-26T15:32:36 Z wasyl Poklon (COCI17_poklon7) C++11
108 / 120
 1000 ms 99952 KB 
#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

# 결과 실행 시간 메모리 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