oj.uz

Submission #408830

# Submission time Handle Problem Language Result Execution time Memory
408830 2021-05-19T17:33:50 Z Jasiekstrz Type Printer (IOI08_printer) C++17
100 / 100
 153 ms 51048 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 13 ms 23812 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23816 KB Output is correct
2 Correct 16 ms 23804 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23812 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 24012 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24140 KB Output is correct
2 Correct 19 ms 24276 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25292 KB Output is correct
2 Correct 31 ms 27212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 27796 KB Output is correct
2 Correct 24 ms 24712 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 33848 KB Output is correct
2 Correct 131 ms 46712 KB Output is correct
3 Correct 90 ms 35936 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 31712 KB Output is correct
2 Correct 153 ms 51048 KB Output is correct
3 Correct 95 ms 37476 KB Output is correct
4 Correct 126 ms 49512 KB Output is correct