Submission #120075

#	Time	Username	Problem	Language	Result	Execution time	Memory
120075		Boxworld	Type Printer (IOI08_printer)	C++14	100 / 100	122 ms	49656 KiB

printer

#include <bits/stdc++.h>
using namespace std;
const int N=500500;
struct TREE{int nxt[26];bool end,mk;}tree[N];
string s,m;
char ss[N],ans[N*2+1];
int S=0,T=0,n,root=0,fin=0;
int newnode(){
	T++;
	memset(tree[T].nxt,-1,sizeof(tree[T].nxt));
	return T;
}
void insert(string x){
	int cnr=root;
	for (int i=0;i<x.length();i++){
		int now=x[i]-'a'; 
		if (tree[cnr].nxt[now]==-1)tree[cnr].nxt[now]=newnode();
		cnr=tree[cnr].nxt[now];
	}
	tree[cnr].end=1;
}
void mark(string x){
	int cnr=root;
	for (int i=0;i<x.length();i++){
		int now=x[i]-'a';
		cnr=tree[cnr].nxt[now];
		tree[cnr].mk=1;
	}
}
void dfs(int cnr){
	if(tree[cnr].end==1)ans[S++]='P';
	int tmp=-1;
	for (int i=0;i<26;i++)
	if (tree[cnr].nxt[i]!=-1){
		int now=tree[cnr].nxt[i];
		if (tree[now].mk!=1){
			ans[S++]=char(i+'a');
			dfs(now);
		}
		else tmp=i;
	}
	if (tmp!=-1){
		ans[S++]=char(tmp+'a');
		dfs(tree[cnr].nxt[tmp]);
	}
	if (tmp==-1&&tree[cnr].mk)fin=1;
	if(!fin)ans[S++]='-';
}
int main(){
	scanf("%d",&n);
	memset(tree[0].nxt,-1,sizeof(tree[0].nxt));
	for (int i=0;i<n;i++){
		scanf("%s",ss);
		string s(ss);
		insert(s);
		if(s.length()>m.length())m=s;
	}
	mark(m);
	dfs(root);
	printf("%d\n",S);
	for (int i=0;i<S;i++)printf("%c\n",ans[i]);
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.length();i++){
               ~^~~~~~~~~~~
printer.cpp: In function 'void mark(std::__cxx11::string)':
printer.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<x.length();i++){
               ~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
printer.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ss);
   ~~~~~^~~~~~~~~

• 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