oj.uz

Submission #531492

# Submission time Handle Problem Language Result Execution time Memory
531492 2022-02-28T22:31:03 Z Pietra Type Printer (IOI08_printer) C++14
30 / 100
 66 ms 19580 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 ; 

	if(fim[v]) return ; 

	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++ ;  
	}

	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('-') ; 

}

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(0, 0) ; 

	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 0 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 19580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 15360 KB Output isn't correct
2 Halted 0 ms 0 KB -