oj.uz

Submission #116552

# Submission time Handle Problem Language Result Execution time Memory
116552 2019-06-12T22:37:19 Z andremfq Type Printer (IOI08_printer) C++17
100 / 100
 178 ms 59104 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())/*	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

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.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
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 #3
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 #4
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 #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3744 KB Output is correct
2 Correct 23 ms 7548 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8944 KB Output is correct
2 Correct 16 ms 2680 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 21736 KB Output is correct
2 Correct 171 ms 49640 KB Output is correct
3 Correct 106 ms 25320 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 17436 KB Output is correct
2 Correct 178 ms 59104 KB Output is correct
3 Correct 106 ms 28740 KB Output is correct
4 Correct 165 ms 55788 KB Output is correct