oj.uz

Submission #837863

# Submission time Handle Problem Language Result Execution time Memory
837863 2023-08-25T19:06:18 Z Liudas Type Printer (IOI08_printer) C++17
100 / 100
 378 ms 101124 KB 
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int MAX_SIZE = 26;
struct node{
    node *arr[MAX_SIZE];
	char val;
    bool end;
	int maxi;
};
node *getNode(){
    node *nnode = new node;
	nnode -> end = 0;
	nnode -> maxi = 0;
	for(int i = 0; i < MAX_SIZE; i ++){
		nnode -> arr[i] = NULL;
	}
	return nnode;
}
void insert_node(node *root, string s){
	node *cur = root;
	for(char i : s){
		int	id = i - 'a';
		if(!cur -> arr[id]){
			cur ->arr[id] = getNode();
		}
		cur = cur -> arr[id];
		cur -> val = i;
	}
	cur -> end = true;
	cur -> maxi = 1;
}
void DFS1(node *root, string s){
	for(int i = 0; i < MAX_SIZE; i ++){
		if(root -> arr[i]){
			DFS1(root -> arr[i], s + char(i +'a'));
			root -> maxi = max((int)root -> arr[i] -> maxi + 1, (int)root -> maxi);
		}
	}
}
void DFS(node *root, string &s){
	for(int i = 0; i < root -> end; i ++){
		s.push_back('P');
	}
	for(int i = 0; i < MAX_SIZE; i ++){
		int best = -1, bc = 1000;
		for(int j = 0; j < MAX_SIZE; j ++){
			if(root -> arr[j]){
				if(root -> arr[j] -> maxi < bc){
					bc = root -> arr[j] -> maxi;
					best = j;
				}
			}
		}
		if(best != -1 && root -> arr[best]){
			root -> arr[best] -> maxi = 10000;
			s.push_back(best+'a');
			DFS(root -> arr[best], s);
		}
	}
	s.push_back('-');
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    node *trie = getNode();
    vector<string> arr(N);
    for(string &i : arr){
        cin >> i;
        insert_node(trie, i);
    }
	string ans;
	DFS1(trie, "");
	DFS(trie, ans);
	cout << int(ans.size()) - trie -> maxi << endl;
	for(int i = 0; i < int(ans.size()) - trie -> maxi; i ++){
		cout << ans[i] << endl;
	}
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 7 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5972 KB Output is correct
2 Correct 45 ms 12688 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14948 KB Output is correct
2 Correct 13 ms 3740 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 37184 KB Output is correct
2 Correct 328 ms 84864 KB Output is correct
3 Correct 164 ms 44516 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 29272 KB Output is correct
2 Correct 371 ms 101124 KB Output is correct
3 Correct 186 ms 50504 KB Output is correct
4 Correct 378 ms 95512 KB Output is correct