oj.uz

Submission #699129

# Submission time Handle Problem Language Result Execution time Memory
699129 2023-02-15T17:24:19 Z Doncho_Bonboncho Type Printer (IOI08_printer) C++14
100 / 100
 125 ms 70836 KB 
#include <bits/stdc++.h>
#include <iterator>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

struct trie{
	int go[26];
	bool word;
	bool big[26];

	trie( ){
		for( int i=0 ; i<26 ; i++ ){
			go[i] = -1;
			big[i] = false;
		}
		word = false;
	}
};	

std::vector<trie> tree;
int size = 1;

void add( const std::string& word, int currNode, int indWord  ){

	if( indWord == word.size() ){
		tree[currNode].word = true;
		return;
	}
	int currW = word[indWord] - 'a';
	if( tree[currNode].go[currW] == -1 ){
		tree[currNode].go[currW] = size;
		tree.push_back(trie());
		size++;
	}
	add( word, tree[currNode].go[currW], indWord +1 );
}


void addBig( const std::string& word, int currNode, int indWord  ){
	if( word.size() == indWord ){
		tree[currNode].word = true;
		return;
	}
	int currW = word[indWord] - 'a';
	if( tree[currNode].go[currW] == -1 ){
		tree[currNode].go[currW] = size;
		tree.push_back(trie());
		size++;
	}

	tree[currNode].big[currW] = true;

	addBig( word, tree[currNode].go[currW], indWord +1 );
}

std::vector<char> nas;
void traverse( int currNode ){
	if( tree[currNode].word  ) nas.push_back('P');

	for( int i=0 ; i<26 ; i++ ){
		if( tree[currNode].go[i] != -1 and !tree[currNode].big[i] ){
			nas.push_back(('a' + i));
			traverse( tree[currNode].go[i] );
			nas.push_back('-');
		}
	}	
	for( int i=0 ; i<26 ; i++ ){
		if( tree[currNode].go[i] != -1 and tree[currNode].big[i] ){
			nas.push_back(('a' + i));
			traverse( tree[currNode].go[i] );
			nas.push_back('-');
		}
	}

}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	
	tree.push_back( trie() );

	std::vector<std::pair<int, std::string>> inp;
	inp.resize(n);
	for( int i=0 ; i<n ; i++ ){
		std::cin>>inp[i].second;
		inp[i].first = inp[i].second.size();
	}

	std::sort( inp.begin(), inp.end() );

	for( int i=0 ; i<n ; i++ ){
	//	add( inp[i].second, 0, 0 );
		if( i != n-1 ) add( inp[i].second, 0, 0 );
		else addBig( inp[i].second, 0, 0 );
	}

	traverse( 0 );

	while( nas.back() == '-' ) nas.pop_back();

	std::cout<<nas.size()<<"\n";
	for( auto j : nas ) std::cout<<j<<"\n";

	return 0;
}

Compilation message

printer.cpp: In function 'void add(const string&, int, int)':
printer.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  if( indWord == word.size() ){
      |      ~~~~~~~~^~~~~~~~~~~~~~
printer.cpp: In function 'void addBig(const string&, int, int)':
printer.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |  if( word.size() == indWord ){
      |      ~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 968 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1472 KB Output is correct
2 Correct 4 ms 2600 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4788 KB Output is correct
2 Correct 20 ms 9280 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9612 KB Output is correct
2 Correct 8 ms 3240 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35372 KB Output is correct
2 Correct 113 ms 70344 KB Output is correct
3 Correct 62 ms 36572 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 18856 KB Output is correct
2 Correct 125 ms 70836 KB Output is correct
3 Correct 74 ms 36912 KB Output is correct
4 Correct 116 ms 70768 KB Output is correct