Submission #1365340

#TimeUsernameProblemLanguageResultExecution timeMemory
1365340shrimbType Printer (IOI08_printer)C++20
100 / 100
111 ms106040 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct ver {
	ver *adj[ 26 ];
	int dep = 0;
	int mx = 0 ;
	
	int cnt= 0;
	ver() {
		for ( int i = 0 ; i < 26 ; i++ ) {
			adj[ i ] = 0 ;
		}
		dep = 0 ;
		cnt = 0 ;
		mx = 0 ;
	}
};
string ans;
ver *root = new ver;
void insert( string s ) {
 ver *cur = root;
	for ( char c : s ) {
		if ( !cur -> adj [ c - 'a' ] ) {
			cur -> adj[ c - 'a' ] = new ver ;

		}
		cur = cur -> adj[ c - 'a'];
	}
	cur -> cnt++;
}

void dfs1 ( ver *cur ) {
  cur -> mx = cur -> dep ;
	cur -> mx = cur -> dep;
	for ( int i = 0 ; i < 26 ; i++ ) {
		//    cout<<adj[ i ]<<' ';
		if ( cur -> adj[ i ] ) {
			cur -> adj[ i ] -> dep = cur -> dep + 1 ;
			dfs1( cur -> adj[ i ]);
			//   cur -> mx = max( cur -> mx , cur -> adj [ i ]);
			cur -> mx = max(cur -> mx, cur -> adj[ i ] -> mx);
		}
	}
}

void dfs2 ( ver *cur ) {
   // while( cur -> cnt-- ){
   //     ans+='P';
   // }
   
	ans += string(cur -> cnt, 'P');

//for ( int i = 0; i < cur -> cnt ; i++ ) {
   // ans +='P';}


	int m = -1 ;
	for ( int i = 0 ; i < 26 ; i++) {
		if ( cur -> adj[ i ] ) {
			//  cout << adj [ i ] << ' ';
			if (m == -1 or cur -> adj[i] -> mx > cur -> adj[ m ] -> mx ) {
				m = i;
			}
		}
	}

	for (int i = 0 ; i < 26 ; i++) {
		if ( i != m and cur -> adj [ i ] ) {
			ans += 'a' + i;
			dfs2(cur -> adj[ i ]);
			ans += '-';
		}
	}

	if (m != -1) {
		ans += 'a' + m;
		dfs2(cur -> adj[ m ]);
		ans += '-';
	}
}



signed main () {
	int n ;
	cin >> n ;

	for ( int i = 0 ; i < n ; i++ ) {
		string s;
		cin >> s;
		insert(s);
	}
	dfs1( root );
	dfs2( root );
	while ( ans.back() == '-' ) {
		ans.pop_back();
	}
	cout << ans.size() << '\n';
	for ( auto c : ans ) {
		cout << c << '\n';
	}

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...