Submission #226384

#	Time	Username	Problem	Language	Result	Execution time	Memory
226384		nafis_shifat	Type Printer (IOI08_printer)	C++14	80 / 100	278 ms	22656 KiB

printer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5+5;
int idx=0;
int trie[mxn][26];
int en[mxn]={};

int depth[mxn];
int cr[mxn];

int pr=0;
int N;
vector<char> ans;
void dfs(int cur)
{
	pr+=en[cur];
	while(en[cur]-- >0)ans.push_back('P');
	vector<int> v;
	for(int i=0;i<26;i++)
	{
		if(trie[cur][i])v.push_back(trie[cur][i]);
	}

	sort(v.begin(),v.end(),[](int a,int b){
		return depth[a]<depth[b];
	});
	for(int i:v)
	{
	    ans.push_back((char)(cr[i]+'a'));
		dfs(i);
	}
	if(pr!=N)ans.push_back('-');

}

void process(int cur)
{
	depth[cur]=1;
	for(int i=0;i<26;i++)
	{
		if(trie[cur][i])
		{
			process(trie[cur][i]);
			depth[cur]=max(depth[cur],depth[trie[cur][i]]+1);
		}
	}
}

void insert(string s)
{
	int cur=0;
	for(char c:s)
	{
		c-='a';
		if(!trie[cur][c])
		{
		    trie[cur][c]=++idx;
		    cr[idx]=c;
		}
		cur=trie[cur][c];
		
	}
	en[cur]++;
}

int main()
{
	cin>>N;

	for(int i=0;i<N;i++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	


	process(0);
	dfs(0);
	cout<<ans.size()<<endl;
	for(char c:ans)cout<<c<<endl;

	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:57:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!trie[cur][c])
                  ^
printer.cpp:59:18: warning: array subscript has type 'char' [-Wchar-subscripts]
       trie[cur][c]=++idx;
                  ^
printer.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   cur=trie[cur][c];
                  ^

• 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: 0 / 10
• Subtask 10: 0 / 10