oj.uz

Submission #105190

# Submission time Handle Problem Language Result Execution time Memory
105190 2019-04-10T23:30:29 Z joseacaz Type Printer (IOI08_printer) C++17
100 / 100
 200 ms 58604 KB 
#include <iostream>
#include <vector>
#include <queue>
#define MAXN 25005
#define pii pair < int, int >
#define mp make_pair

using namespace std;
typedef long long int lld;

struct trie
{
	int child[26], maxSize = 0;
	bool finish = 0;
};

int N, C = 1, answer;
string word;
trie Trie[MAXN * 20];
vector < char > ans;

void add ( string s )
{
	int node = 0, let = 0;
	for ( int i = 0; i < s.length(); i++ )
	{
		let = s[i] - 'a';

		if ( !Trie[node].child[let] )
			Trie[node].child[let] = C++;
		node = Trie[node].child[let];

		Trie[node].maxSize = max ( Trie[node].maxSize, int(s.length() - i) );
	}
	Trie[node].finish = 1;
}

void solve ( int node )
{
	int nextNode = 0;
	priority_queue < pii > PQ;
	for ( int i = 0; i < 26; i++ )
	{
		nextNode = Trie[node].child[i];
		if ( nextNode )
			PQ.push ( mp ( -Trie[nextNode].maxSize, i ) );
	}

	if ( Trie[node].finish )
		ans.push_back ( 'P' );

	while ( !PQ.empty() )
	{
		ans.push_back( char(PQ.top().second + 'a') );
		solve ( Trie[node].child[PQ.top().second] );
		ans.push_back ( '-' );
		PQ.pop();
	}
}

int main ()
{
	cin >> N;
	for ( int i = 0; i < N; i++ )
		cin >> word, add ( word );
	
	solve ( 0 );

	answer = ans.size();

	for ( int i = answer - 1; i >= 0; i-- )
	{
		if ( ans[i] != '-')
			break;
		answer = i;
	}

	cout << answer << "\n";
	for ( int i = 0; i < answer; i++ )
		cout << ans[i] << "\n";
	return 0;
}

Compilation message

printer.cpp: In function 'void add(std::__cxx11::string)':
printer.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for ( int i = 0; i < s.length(); i++ )
                   ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 55160 KB Output is correct
2 Correct 40 ms 55160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55164 KB Output is correct
2 Correct 46 ms 55132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 55112 KB Output is correct
2 Correct 48 ms 55160 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 55104 KB Output is correct
2 Correct 45 ms 55040 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55132 KB Output is correct
2 Correct 51 ms 55272 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 55236 KB Output is correct
2 Correct 46 ms 55288 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 55416 KB Output is correct
2 Correct 58 ms 55672 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 55740 KB Output is correct
2 Correct 50 ms 55488 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 56524 KB Output is correct
2 Correct 148 ms 57960 KB Output is correct
3 Correct 109 ms 56816 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 56312 KB Output is correct
2 Correct 200 ms 58604 KB Output is correct
3 Correct 115 ms 57072 KB Output is correct
4 Correct 200 ms 58400 KB Output is correct