oj.uz

Submission #1062376

# Submission time Handle Problem Language Result Execution time Memory
1062376 2024-08-17T05:12:48 Z tamir1 Type Printer (IOI08_printer) C++17
100 / 100
 124 ms 113464 KB 
#include<bits/stdc++.h>
using namespace std;
string s,ans;
int n,mx;
struct mod{
	mod *node[30];
	bool togsgol;
	int x;
	mod(){
		x=0;
		for(int i=0;i<=26;i++){
			node[i]=NULL;
		}
		togsgol=0;
	}
};
int dfs(mod *root){
	int mx=0;
	if(root==NULL) return 0;
	for(int i=0;i<26;i++){
		int y=dfs(root->node[i]);
		if(mx<y){
			mx=y;
			root->x=i;
		}
	}
	return mx+1;
}
void solve(mod *root){
	if(root->togsgol) ans.push_back('P');
	for(int i=0;i<26;i++){
		if(i!=root->x && root->node[i]!=NULL){
			ans.push_back(i+'a');
			solve(root->node[i]);
		}
	}
	if(root->node[root->x]!=NULL){
		ans.push_back(root->x+'a');
		solve(root->node[root->x]);
	}
	ans.push_back('-');
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	mod *root = new mod();
	mod *root1=root;
	for(int i=0;i<n;i++){
		cin >> s;
		int m=s.size();
		root1=root;
		for(int j=0;j<m;j++){
			if(root1->node[s[j]-'a']==NULL){
				root1->node[s[j]-'a']=new mod();
				root1=root1->node[s[j]-'a'];
			}
			else root1=root1->node[s[j]-'a'];
		}
		root1->togsgol=1;
		mx=max(mx,m);
	}
	root1=root;
	dfs(root1);
	solve(root1);
	while(ans.back()=='-') ans.pop_back();
	cout << ans.size() << "\n";
	for(int i=0;i<ans.size();i++) cout << ans[i] << "\n";
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=0;i<ans.size();i++) cout << ans[i] << "\n";
      |              ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6748 KB Output is correct
2 Correct 16 ms 14172 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16876 KB Output is correct
2 Correct 6 ms 3928 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 41628 KB Output is correct
2 Correct 109 ms 95260 KB Output is correct
3 Correct 56 ms 49140 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 32496 KB Output is correct
2 Correct 124 ms 113464 KB Output is correct
3 Correct 62 ms 55792 KB Output is correct
4 Correct 107 ms 106956 KB Output is correct