oj.uz

Submission #299579

# Submission time Handle Problem Language Result Execution time Memory
299579 2020-09-15T09:13:27 Z AMO5 Type Printer (IOI08_printer) C++17
100 / 100
 212 ms 58576 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define eb emplace_back
#define ii pair<int,int>

struct tr{
	bool prt=0;
	int len=0;
	int nxt[26];
	tr(){
		prt=0;
		fill(begin(nxt),end(nxt),-1);
	}
};

vector<tr>trie;

void insert(string s){
	int n=s.length();
	int k=0;
	for(int i=0; i<n; i++){
		int j = s[i]-'a';
		if(trie[k].nxt[j]==-1){
			trie[k].nxt[j]=sz(trie);
			trie.emplace_back();
		}
		trie[k].len=max(trie[k].len,n);
		k=trie[k].nxt[j];
	}
	trie[k].len=max(trie[k].len,n);
	trie[k].prt=1;
	return;
}

vector<char>ans;

void dfs(int u=0){
	if(trie[u].prt)ans.eb('P');
	vector<ii>vv;
	for(int i=0; i<26; i++){
		if(trie[u].nxt[i]!=-1){
			vv.eb(trie[trie[u].nxt[i]].len,i);
		}
	}
	sort(vv.begin(),vv.end());
	for(ii x:vv){
		ans.eb(char('a'+x.second));
		dfs(trie[u].nxt[x.second]);
	}
	ans.eb('-');
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	trie.eb();
	int n;
	cin>>n;
	string s;
	for(int i=0; i<n; i++){
		cin>>s;
		insert(s);
	}
	dfs();
	while(ans.back()=='-'){
		ans.pop_back();
	}
	cout<<sz(ans)<<"\n";
	for(char c:ans)cout<<c<<"\n";
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4084 KB Output is correct
2 Correct 33 ms 7792 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8044 KB Output is correct
2 Correct 12 ms 2424 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 29532 KB Output is correct
2 Correct 195 ms 58408 KB Output is correct
3 Correct 97 ms 29652 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 15532 KB Output is correct
2 Correct 212 ms 58532 KB Output is correct
3 Correct 112 ms 29672 KB Output is correct
4 Correct 192 ms 58576 KB Output is correct