Submission #1176521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176521		StefanSebez	Type Printer (IOI08_printer)	C++20	100 / 100	635 ms	54572 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,lg=27;
int nc,go[N][lg+1],root,kraj[N],dubina[N];
void Update(int &c,string s,int i=0){
	if(!c)c=++nc;
	if(i==s.size()){kraj[c]++;dubina[c]=max(dubina[c],i);return;}
	int x=s[i]-'a';
	Update(go[c][x],s,i+1);
	for(int j=0;j<lg;j++) dubina[c]=max(dubina[c],dubina[go[c][j]]);
}
vector<char>res;
void DFS(int c){
	while(kraj[c]--) res.pb('P');
	int ind=-1,maks=0;
	for(int i=0;i<lg;i++){
		if(dubina[go[c][i]]>maks){
			ind=i;
			maks=dubina[go[c][i]];
		}
	}
	for(int i=0;i<26;i++){
		if(i==ind) continue;
		if(go[c][i]){
			res.pb('a'+i);
			DFS(go[c][i]);
			res.pb('-');
		}
	}
	if(ind!=-1){
		res.pb('a'+ind);
		DFS(go[c][ind]);
		res.pb('-');
	}
}
int main(){
    int n;scanf("%i",&n);
    for(int i=1;i<=n;i++){
		string s;cin>>s;
		Update(root,s);
    }
    DFS(root);
    while(res.back()=='-') res.pop_back();
    printf("%i\n",res.size());
    for(auto c:res) cout<<c<<endl;
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:49:14: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wformat=]
   49 |     printf("%i\n",res.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<char>::size_type {aka long unsigned int}
      |             %li
printer.cpp:42:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10