oj.uz

Submission #226387

# Submission time Handle Problem Language Result Execution time Memory
226387 2020-04-23T16:41:44 Z nafis_shifat Type Printer (IOI08_printer) C++14
100 / 100
 166 ms 52844 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=5e5+5;
int idx=0;
int trie[mxn][26];
int en[mxn]={};

int depth[mxn];
int cr[mxn];

int pr=0;
int N;
vector<char> ans;
char s[23];
void dfs(int cur)
{
	pr+=en[cur];
	while(en[cur]-- >0)ans.push_back('P');
	vector<int> v;
	for(int i=0;i<26;i++)
	{
		if(trie[cur][i])v.push_back(trie[cur][i]);
	}

	sort(v.begin(),v.end(),[](int a,int b){
		return depth[a]<depth[b];
	});
	for(int i:v)
	{
	    ans.push_back((char)(cr[i]+'a'));
		dfs(i);
	}
	if(pr!=N)ans.push_back('-');

}

void process(int cur)
{
	depth[cur]=1;
	for(int i=0;i<26;i++)
	{
		if(trie[cur][i])
		{
			process(trie[cur][i]);
			depth[cur]=max(depth[cur],depth[trie[cur][i]]+1);
		}
	}
}

void insert()
{
	int cur=0;
	int n=strlen(s);
	for(int i=0;i<n;i++)
	{
	    char c=s[i];
		c-='a';
		if(!trie[cur][c])
		{
		    trie[cur][c]=++idx;
		    cr[idx]=c;
		}
		cur=trie[cur][c];
		
	}
	en[cur]++;
}

int main()
{
	cin>>N;

	for(int i=0;i<N;i++)
	{
		scanf("%s",s);
		insert();
	}
	


	process(0);
	dfs(0);
	cout<<ans.size()<<endl;
	for(char c:ans)printf("%c\n",c);

	return 0;
}

Compilation message

printer.cpp: In function 'void insert()':
printer.cpp:60:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!trie[cur][c])
                  ^
printer.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
       trie[cur][c]=++idx;
                  ^
printer.cpp:65:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   cur=trie[cur][c];
                  ^
printer.cpp: In function 'int main()':
printer.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
   ~~~~~^~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1152 KB Output is correct
2 Correct 8 ms 1384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3328 KB Output is correct
2 Correct 26 ms 6936 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8060 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 19576 KB Output is correct
2 Correct 154 ms 44520 KB Output is correct
3 Correct 79 ms 23696 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 15344 KB Output is correct
2 Correct 166 ms 52844 KB Output is correct
3 Correct 96 ms 26732 KB Output is correct
4 Correct 146 ms 50460 KB Output is correct