Submission #226387

#	Time	Username	Problem	Language	Result	Execution time	Memory
226387		nafis_shifat	Type Printer (IOI08_printer)	C++14	100 / 100	166 ms	52844 KiB

printer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=5e5+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;
char s[23];
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()
{
	int cur=0;
	int n=strlen(s);
	for(int i=0;i<n;i++)
	{
	    char c=s[i];
		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++)
	{
		scanf("%s",s);
		insert();
	}
	


	process(0);
	dfs(0);
	cout<<ans.size()<<endl;
	for(char c:ans)printf("%c\n",c);

	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void insert()':
printer.cpp:60:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!trie[cur][c])
                  ^
printer.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
       trie[cur][c]=++idx;
                  ^
printer.cpp:65:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   cur=trie[cur][c];
                  ^
printer.cpp: In function 'int main()':
printer.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
   ~~~~~^~~~~~~~

• 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