oj.uz

Submission #915025

# Submission time Handle Problem Language Result Execution time Memory
915025 2024-01-23T08:10:08 Z allin27x Type Printer (IOI08_printer) C++17
100 / 100
 138 ms 99640 KB 
#include <bits/stdc++.h>
using namespace std;


struct prtr{
	prtr* r[26] {nullptr};
	bool last = 0;
	bool end = 0;
};

vector<char> ans;


void add(string s, prtr* root){
	for (int i=0; i<s.size(); i++){
		if (!(root -> r[s[i]-'a'])) root->r[s[i]-'a'] = new prtr();
		root = root->r[s[i]-'a'];
	}
	root -> end = 1;
}

void make_last(string s, prtr* root){
	for (int i=0; i<s.size(); i++){
		if (!(root -> r[s[i]-'a'])) root->r[s[i]-'a'] = new prtr();
		root = root->r[s[i]-'a'];
		root -> last = 1;
	}
}

void dfs(prtr* root){
	int l = -1;
	if (root->end) ans.push_back('P');
	for (int i=0; i<26; i++){
		if (!root->r[i]) continue;
		if (root->r[i]->last) {l=i; continue;}
		ans.push_back('a'+i);
		dfs(root->r[i]);
		ans.push_back('-');
	}
	if (l==-1) return;
	ans.push_back('a'+l);
	dfs(root->r[l]);
}

int main(){
	int n; cin>>n;
	prtr* root = new prtr();
	int mxsz = 0; string mw = "";
	while (n--){
		string s; cin>>s;
		if (s.size()>=mxsz) mxsz = s.size(), mw = s;
		add(s, root);
	}
	make_last(mw,root);
	dfs(root);

	cout<<ans.size()<<'\n';
	for (int i=0; i<ans.size(); i++){
		cout<<ans[i]<<'\n';
	}
}

Compilation message

printer.cpp: In function 'void add(std::string, prtr*)':
printer.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for (int i=0; i<s.size(); i++){
      |                ~^~~~~~~~~
printer.cpp: In function 'void make_last(std::string, prtr*)':
printer.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int i=0; i<s.size(); i++){
      |                ~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:51:15: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   if (s.size()>=mxsz) mxsz = s.size(), mw = s;
      |       ~~~~~~~~^~~~~~
printer.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i=0; i<ans.size(); i++){
      |                ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5976 KB Output is correct
2 Correct 16 ms 12480 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 14812 KB Output is correct
2 Correct 9 ms 3472 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 36704 KB Output is correct
2 Correct 115 ms 83656 KB Output is correct
3 Correct 61 ms 43316 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 28632 KB Output is correct
2 Correct 138 ms 99640 KB Output is correct
3 Correct 73 ms 49104 KB Output is correct
4 Correct 112 ms 94156 KB Output is correct