oj.uz

Submission #226385

# Submission time Handle Problem Language Result Execution time Memory
226385 2020-04-23T16:37:18 Z nafis_shifat Type Printer (IOI08_printer) C++14
80 / 100
 1000 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;
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(string s)
{
	int cur=0;
	for(char c:s)
	{
		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++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	


	process(0);
	dfs(0);
	cout<<ans.size()<<endl;
	for(char c:ans)cout<<c<<endl;

	return 0;
}

Compilation message

printer.cpp: In function 'void insert(std::__cxx11::string)':
printer.cpp:57:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!trie[cur][c])
                  ^
printer.cpp:59:18: warning: array subscript has type 'char' [-Wchar-subscripts]
       trie[cur][c]=++idx;
                  ^
printer.cpp:62:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   cur=trie[cur][c];
                  ^

Subtask #1
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 #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 640 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 5 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1152 KB Output is correct
2 Correct 41 ms 1408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 3328 KB Output is correct
2 Correct 244 ms 7160 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 8056 KB Output is correct
2 Correct 87 ms 1920 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 19704 KB Output is correct
2 Execution timed out 1095 ms 44652 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 15472 KB Output is correct
2 Execution timed out 1092 ms 52844 KB Time limit exceeded
3 Halted 0 ms 0 KB -