oj.uz

Submission #531503

# Submission time Handle Problem Language Result Execution time Memory
531503 2022-03-01T00:18:57 Z Pietra Type Printer (IOI08_printer) C++14
100 / 100
 161 ms 54976 KB 
#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 28*25005 ; 

int n, fim[maxn], trie[maxn][28], qtd_pal, mx[maxn], ct ; 
string s ; 
vector<char> ans ; 

void add(string s){

	int root = 0 ; 

	for(int i = 0 ; i < s.size() ; i++){
		if(!trie[root][s[i]-'a']) trie[root][s[i]-'a'] = ++ct ; 
		root = trie[root][s[i]-'a'] ; 
	}

	fim[root] = 1 ; 

}

void dfs_alt(int v, int p){

	mx[v] = 1 ; 

	for(char i = 'a' ; i <= 'z' ; i++){
		if(!trie[v][i-'a'] || trie[v][i-'a'] == p) continue ; 
		dfs_alt(trie[v][i-'a'], v) ; 
		mx[v] = max(mx[v], mx[trie[v][i-'a']] + 1) ;  
	}

}

void dfs(int v, int p){

	if(fim[v]){
		ans.push_back('P') ;
		qtd_pal += fim[v] ;  
	}

	int mxx = -1 ; char ind = 0 ;

	for(char i = 'a' ; i <= 'z' ; i++){
		if(!trie[v][i-'a'] || trie[v][i-'a'] == p) continue ; 
		if(mxx < mx[trie[v][i-'a']]){
			mxx = mx[trie[v][i-'a']] ; ind = i ; 
		}
	} 

	for(char i = 'a' ; i <= 'z' ; i++){
		if(!trie[v][i-'a'] || trie[v][i-'a'] == p || i == ind) continue ; 
		ans.push_back(i) ; 
		dfs(trie[v][i-'a'], v) ; 
 	}

 	if(mxx != -1 && trie[v][ind-'a']){
 		ans.push_back(ind) ; 
 		dfs(trie[v][ind-'a'], v) ; 
 	
}
	if(qtd_pal != n) ans.push_back('-') ; 

}

// void dfs_view(int v, int p){

// 	for(char i = 'a' ; i <= 'z' ; i++){
// 		if(!trie[v][i-'a'] || trie[v][i-'a'] == p) continue ; 
// 		cout << trie[v][i-'a'] << " " << i << "\n" ; 
// 		dfs_view(trie[v][i-'a'] , v) ;
// 	} 

// }

int main(){

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

	cin >> n ; 

	for(int i = 1 ; i <= n ; i++){
		cin >> s ; 
		add(s) ; 
	}

	dfs_alt(0, 0) ; 

	// dfs_view(0, 0) ; 

	dfs(0, 0) ; 

	// for(int i = 0 ; i <= 8 ; i++) cout << mx[i] << " " ; 

	// cout << "\n" ; 

	cout << ans.size() << "\n" ; 

	for(auto a : ans) cout << a << "\n" ; 

}

Compilation message

printer.cpp: In function 'void add(std::string)':
printer.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0 ; i < s.size() ; i++){
      |                  ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3404 KB Output is correct
2 Correct 21 ms 7068 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8364 KB Output is correct
2 Correct 7 ms 2124 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 20424 KB Output is correct
2 Correct 141 ms 46440 KB Output is correct
3 Correct 73 ms 24044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16068 KB Output is correct
2 Correct 161 ms 54976 KB Output is correct
3 Correct 84 ms 27260 KB Output is correct
4 Correct 146 ms 52124 KB Output is correct