oj.uz

Submission #676658

# Submission time Handle Problem Language Result Execution time Memory
676658 2022-12-31T15:44:23 Z QwertyPi Type Printer (IOI08_printer) C++14
90 / 100
 1000 ms 62404 KB 
#include <bits/stdc++.h>

using namespace std;

const int SIGMA = 26; 
int ncnt = 0;
struct node{
	int nxt[SIGMA] = {};
	bool word = false;
	int heavy = -1; 
	node() {}
	int extend(int c){
		if(!nxt[c]) nxt[c] = ++ncnt;
		return nxt[c];
	}
	int extend_heavy(int c){
		heavy = c;
		return nxt[c];
	}
};

const int MAXN = 25011;
node trie[MAXN * 21];

string ans;
void dfs(int root){
	if(trie[root].word) ans.push_back('P');
	for(int c = 0; c < SIGMA; c++){
		if(trie[root].nxt[c] && trie[root].heavy != c){
			ans.push_back('a' + c);
			dfs(trie[root].nxt[c]);
			ans.push_back('-');
		}
	}
	if(trie[root].heavy != -1){
		ans.push_back('a' + trie[root].heavy);
		dfs(trie[root].nxt[trie[root].heavy]);
		ans.push_back('-');
	}
}

int root = 0;
int main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n; cin >> n;
	vector<string> vs;
	for(int i = 0; i < n; i++){
		string s; cin >> s;
		vs.push_back(s);
		int x = root;
		for(auto c : s){
			x = trie[x].extend(c - 'a');
		}
		trie[x].word = true;
	}
	
	int idx = 0;
	for(int i = 1; i < n; i++){
		if(vs[i].size() > vs[idx].size()){
			idx = i;
		}
	}
	{
		int x = root;
		for(auto c : vs[idx]){
			x = trie[x].extend_heavy(c - 'a');
		}
	}
	dfs(root);
	while(ans.back() == '-') ans.pop_back();
	cout << ans.size() << endl;
	for(auto c : ans) cout << c << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 57804 KB Output is correct
2 Correct 26 ms 57828 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 57824 KB Output is correct
2 Correct 26 ms 57860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 57860 KB Output is correct
2 Correct 26 ms 57796 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 57816 KB Output is correct
2 Correct 26 ms 57852 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 57892 KB Output is correct
2 Correct 35 ms 57884 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 57960 KB Output is correct
2 Correct 47 ms 57940 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 58188 KB Output is correct
2 Correct 157 ms 58564 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 58744 KB Output is correct
2 Correct 74 ms 58532 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 60076 KB Output is correct
2 Correct 864 ms 61668 KB Output is correct
3 Correct 465 ms 60856 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 59864 KB Output is correct
2 Execution timed out 1018 ms 62404 KB Time limit exceeded
3 Halted 0 ms 0 KB -