oj.uz

Submission #739605

# Submission time Handle Problem Language Result Execution time Memory
739605 2023-05-10T18:32:56 Z MODDI Type Printer (IOI08_printer) C++14
100 / 100
 148 ms 108360 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
int n;
vector<string> str;
struct trie{
	trie* children[26]={};
	int last = 69, mxd = -1;
	bool leaf = false;
};
void trie_add(trie* root, string s){
	trie* cur = root;
	for(int i = 0; i < s.size(); i++){
		int c = s[i] - 'a';
		if(cur->children[c] == NULL)
			cur->children[c] = new trie;
		if(ckmax(cur->mxd, (int)s.size() - i -1))
			cur-> last = c;
			
		cur = cur->children[c];
	}	
	cur->leaf = true;
}
vector<char> ans;
void dfs(trie* root){
	if(root->leaf)	ans.pb('P');
	for(int i = 0; i < 26; i++){
		if(root->children[i] != NULL && i != root->last){
			ans.pb(char(i + 'a'));
			dfs(root->children[i]);
		}
	}
	if(root->last != 69){
		ans.pb(char(root->last +'a'));
		dfs(root->children[root->last]);
	}
	ans.pb('-');
}
int main(){
	cin>>n;
	str.resize(n);
	for(int i = 0; i < n; i++)
		cin>>str[i];
		
	trie t;
	for(auto i : str){
		trie_add(&t, i);
	}
	dfs(&t);
	while(ans.back() == '-')	ans.pop_back();
	cout<<ans.size()<<endl;
	for(auto t : ans)
		cout<<t<<'\n';
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 2 ms 1204 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15912 KB Output is correct
2 Correct 11 ms 4024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 39652 KB Output is correct
2 Correct 131 ms 91204 KB Output is correct
3 Correct 71 ms 47780 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31180 KB Output is correct
2 Correct 148 ms 108360 KB Output is correct
3 Correct 88 ms 54300 KB Output is correct
4 Correct 138 ms 102372 KB Output is correct