oj.uz

Submission #718216

# Submission time Handle Problem Language Result Execution time Memory
718216 2023-04-03T16:40:25 Z APROHACK Type Printer (IOI08_printer) C++14
100 / 100
 152 ms 76092 KB 
#include<bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
using namespace std;
vector<string>vec;
int trie[25*25000][29];//27 for 'P', 28 for size
int cur = 1;
vector<char>ans;
void insert(int node, string &s, int pos){
	if(pos == s.size()){
		trie[node][28] = 1;
		return ;
	}
	//cout << "estamos en node = " << node << "calculando " <<s[pos] << endl; 
	int nxt = (s[pos] >= 'a' ? s[pos]-'a' : 27);
	if(trie[node][nxt] == -1){
		trie[node][nxt] = cur++;
	}	
	insert(trie[node][nxt], s, pos+1);
	trie[node][28] = max(trie[node][28], trie[trie[node][nxt]][28]+1);
}

void recorrer(int node, bool esP){
	int mx = -1, cual = -1;
	for(int i = 0 ; i <= 27 ; i++){
		if(trie[node][i] != -1){
			if(trie[trie[node][i]][28] > mx){
				mx = trie[trie[node][i]][28];
				cual = i;
			}
		}
	}
	for(int i = 0 ; i <= 27 ; i++){
		if(trie[node][i] != -1 and i != cual){
			ans.pb( (i < 27 ? 'a' + i : 'P'));
			recorrer(trie[node][i], i == 27);
		}
	}
	if(cual != -1){
		ans.pb( (cual < 27 ? 'a' + cual : 'P'));
		recorrer(trie[node][cual], cual == 27);
	}
	if(!esP)ans.pb('-');
}



int main(){
	//freopen("input.txt", "r", stdin);
	int n;
	memset(trie, -1, sizeof trie);
	cin>>n;
	string s;
	for(int i = 0 ; i < n ; i ++){
		cin>>s;
		vec.pb(s);
		s+="P";
		insert(0, s, 0);
	}
	recorrer(0, true);
	while(ans.back() == '-')ans.pop_back();
	cout << ans.size() << "\n";
	for(auto i : ans){
		cout << i << "\n";
	}
	
	
}

Compilation message

printer.cpp: In function 'void insert(int, std::string&, int)':
printer.cpp:12:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  if(pos == s.size()){
      |     ~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 71124 KB Output is correct
2 Correct 29 ms 71196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 71120 KB Output is correct
2 Correct 28 ms 71224 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 71116 KB Output is correct
2 Correct 29 ms 71124 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 71116 KB Output is correct
2 Correct 28 ms 71124 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 71152 KB Output is correct
2 Correct 28 ms 71160 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 71296 KB Output is correct
2 Correct 30 ms 71244 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 71568 KB Output is correct
2 Correct 47 ms 71900 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 72216 KB Output is correct
2 Correct 45 ms 72008 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 73628 KB Output is correct
2 Correct 141 ms 75300 KB Output is correct
3 Correct 97 ms 74680 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 73452 KB Output is correct
2 Correct 152 ms 76092 KB Output is correct
3 Correct 116 ms 75076 KB Output is correct
4 Correct 152 ms 75936 KB Output is correct