Submission #837839

#	Time	Username	Problem	Language	Result	Execution time	Memory
837839		Liudas	Type Printer (IOI08_printer)	C++17	100 / 100	173 ms	107912 KiB

printer

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int MAX_SIZE = 27;
struct node{
    node *arr[MAX_SIZE];
    char val;
    int 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 -> end ++;
	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(root -> arr[i] -> maxi + 1, root -> maxi);
		}
	}
}
void DFS(node *root, string &s){
	vector<int> order;
	for(int i = 0; i < MAX_SIZE; i ++){
		if(root -> arr[i])order.push_back(i);
	}
	for(int i = 0; i < root -> end; i ++){
		s.push_back('P');
	}
	sort(order.begin(), order.end(), [&](int a, int b){return root -> arr[a] -> maxi < root -> arr[b] -> maxi;});
	for(int i : order){
		s.push_back(i+'a');
		DFS(root -> arr[i], 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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10