oj.uz

Submission #115189

# Submission time Handle Problem Language Result Execution time Memory
115189 2019-06-05T23:17:59 Z ly20 Type Printer (IOI08_printer) C++14
100 / 100
 177 ms 61540 KB 
#include<bits/stdc++.h>
using namespace std;
#define debug(args...) //fprintf(stderr,args)
const int MAXN=25010,MAXL=30;
int trie[MAXN*MAXL][MAXL],vl[MAXN*MAXL],cont[MAXN*MAXL],pos[MAXN*MAXL],end1[MAXN*MAXL],pt[MAXN*MAXL];
int at;
vector<char> rs;
string s1;
string sr;
int tmn;
void tr(int v)
{
	for(int i=0;i<MAXL;i++)
	{
		if(trie[v][i]!=0 && pt[trie[v][i]]!=1)
		{
			rs.push_back(vl[trie[v][i]]+'a');
			if(end1[trie[v][i]])rs.push_back('P');
			tr(trie[v][i]);
			rs.push_back('-');
		}
	}
	int id;
	if(tmn>pos[v])
	{
		id=sr[pos[v]]-'a';
		if(pt[trie[v][id]]==1)
		{
			rs.push_back(vl[trie[v][id]]+'a');
			if(end1[trie[v][id]])rs.push_back('P');
			tr(trie[v][id]);
		}
	}
}
void add(string s)
{
	int cur=0;
	int tm=s.size();
	for(int i=0;i<tm;i++)
	{
		cont[cur]++;
		int id=s[i]-'a';
		if(trie[cur][id]==0)
		{
			trie[cur][id]=++at;
			vl[at]=id;
			pos[at]=i+1;
		}
		cur=trie[cur][id];
	}
	end1[cur]=1;
}
void pt1(string s)
{
	int cur=0;
	int tm=s.size();
	for(int i=0;i<tm;i++)
	{
		int id=s[i]-'a';
		cur=trie[cur][id];
		pt[cur]=1;
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		cin>>s1;
		if(s1.size()>sr.size())sr=s1;
		add(s1);
	}
	pt1(sr);
	tmn=sr.size();
	tr(0);
	printf("%d\n",rs.size());
	for(int i=0;i<rs.size();i++)printf("%c\n",rs[i]);
	return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:77:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n",rs.size());
                ~~~~~~~~~^
printer.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<rs.size();i++)printf("%c\n",rs[i]);
              ~^~~~~~~~~~
printer.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~

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 512 KB Output is correct
2 Correct 3 ms 896 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3968 KB Output is correct
2 Correct 23 ms 7928 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9332 KB Output is correct
2 Correct 15 ms 2304 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22812 KB Output is correct
2 Correct 140 ms 51788 KB Output is correct
3 Correct 82 ms 27120 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17904 KB Output is correct
2 Correct 177 ms 61540 KB Output is correct
3 Correct 91 ms 30704 KB Output is correct
4 Correct 135 ms 58608 KB Output is correct