oj.uz

Submission #116551

# Submission time Handle Problem Language Result Execution time Memory
116551 2019-06-12T22:26:17 Z andremfq Type Printer (IOI08_printer) C++17
10 / 100
 69 ms 21720 KB 
#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())	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 && 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,0);
	
	dfs(1,v[0][0]-'a');
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1280 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3840 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 8824 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 21720 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 17260 KB printed invalid word
2 Halted 0 ms 0 KB -