Submission #408830

#	Time	Username	Problem	Language	Result	Execution time	Memory
408830		Jasiekstrz	Type Printer (IOI08_printer)	C++17	100 / 100	153 ms	51048 KiB

printer

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int M=5e5;
map<char,int> e[M+10];
int en[M+10];
int mx[M+10];
void add(int x,string &s,int i,int &m)
{
	if(i==s.size())
	{
		en[x]++;
		mx[x]=max(mx[x],i);
		return;
	}
	if(e[x][s[i]]==0)
		e[x][s[i]]=++m;
	add(e[x][s[i]],s,i+1,m);
	mx[x]=max(mx[x],mx[e[x][s[i]]]);
	return;
}
void dfs(int x,string &s,bool all)
{
	while(en[x]--)
		s+='P';
	if(e[x].empty())
		return;
	int mxx=-1;
	char g='a';
	for(auto v:e[x])
	{
		if(mx[v.se]>mxx)
		{
			mxx=mx[v.se];
			g=v.fi;
		}
	}
	for(auto v:e[x])
	{
		if(v.fi!=g)
		{
			s+=v.fi;
			dfs(v.se,s,true);
			s+='-';
		}
	}
	s+=g;
	dfs(e[x][g],s,all);
	if(all)
		s+='-';
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m=1;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string s;
		cin>>s;
		add(1,s,0,m);
	}
	string ans;
	dfs(1,ans,false);
	cout<<ans.size()<<"\n";
	for(auto v:ans)
		cout<<v<<"\n";
	return 0;
}

Compilation message (stderr)

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

• 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