Submission #116552

#	Time	Username	Problem	Language	Result	Execution time	Memory
116552		andremfq	Type Printer (IOI08_printer)	C++17	100 / 100	178 ms	59104 KiB

printer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=25010,	ALF=30;

int n,trie[MAXN*ALF][ALF],marc[MAXN*ALF],endi[MAXN*ALF],cnt=1,ok;
vector<string> v;
char aux[30];

void add(string w)
{
	int cur=0,ID=w[0]-'a';
	
	for(int i=0;i<w.size();i++)
	{
		int id=w[i]-'a';
		if(trie[cur][id]==0)	trie[cur][id]=cnt,	cnt++;
		cur=trie[cur][id];
	}
	
	endi[cur]=1;
}

void dfs(int cur,int bla)
{
	marc[cur]=1;
	
	if(cur==v[0].size())/*	printf("LETRA FINAL : %c\n",bla+'a'),*/	ok=1;
	
	if(cur)	printf("%c\n",bla+'a');
	if(endi[cur])	printf("P\n");

	vector<pair<int,int> > blabla;
	for(int i=0;i<26;i++)
	{
		int viz=trie[cur][i];
		if(marc[viz]==1)	continue;
		blabla.push_back(make_pair(viz,i));
	}
	
	sort(blabla.begin(),blabla.end());
	
	for(int i=blabla.size()-1;i>=0;i--)
		dfs(blabla[i].first,blabla[i].second);
	
	if(bla!=-1 && ok==0)	printf("-\n");
}

bool cmp(string a,string b)
{
	return a.size()>b.size();
}

int main ()
{
	scanf("%d",&n);
	
	for(int i=0;i<n;i++)
		scanf(" %s",aux),	v.push_back((string)aux);
	
	sort(v.begin(),v.end(),cmp);
	
	for(int i=0;i<n;i++)	add(v[i]);
	
	printf("%d\n",(cnt-1)*2+n-v[0].size());
	
	marc[1]=1;
	dfs(0,-1);
	
//	printf("LETRA : %c\n",v[0][0]);
	dfs(1,v[0][0]-'a');
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::__cxx11::string)':
printer.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w.size();i++)
              ~^~~~~~~~~
printer.cpp:11:12: warning: unused variable 'ID' [-Wunused-variable]
  int cur=0,ID=w[0]-'a';
            ^~
printer.cpp: In function 'void dfs(int, int)':
printer.cpp:27:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(cur==v[0].size())/* printf("LETRA FINAL : %c\n",bla+'a'),*/ ok=1;
     ~~~^~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:64:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::__cxx11::basic_string<char>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",(cnt-1)*2+n-v[0].size());
                ~~~~~~~~~~~~~~~~~~~~~~~^
printer.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
printer.cpp:58:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",aux), v.push_back((string)aux);
   ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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