제출 #1312980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312980		zeyyy	Type Printer (IOI08_printer)	C++20	100 / 100	156 ms	133056 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node {
	Node* links[26];
	vector<pair<int,int>> best;
	bool end = false;
	int countPrefix = 0, countEnds = 0;
	bool containsKey(char c) {
		return links[c - 'a'] != nullptr && links[c - 'a']->countPrefix > 0;
	}
	void put(char c, Node* node) {
		links[c - 'a'] = node;
	}
	Node* get(char c) {
		return links[c - 'a'];
	}
};
struct Trie {
	Node* root;
	Trie() {
		root = new Node();
	}
	void insert(string word) {
		Node* node = root;
		for (int i = 0; i<word.length(); ++i) {
			if (!node->containsKey(word[i]))
				node->put(word[i], new Node());
			node = node->get(word[i]);
			node->countPrefix++;
		}
		node->countEnds++;
	}
	void erase(string word) {
		Node* node = root;
		for (int i = 0; i<word.length(); ++i) {
			if (!node->containsKey(word[i]))
				return;
			node = node->get(word[i]);
			node->countPrefix--;
		}
		node->countEnds--;
	}
	int search(string word) {
		Node* node = root;
		for (int i = 0; i<word.length(); ++i) {
			node = node->get(word[i]);
			if (node->countPrefix == 1) return i;
		}
		return word.length();
	}
};
auto trie = new Trie();
vector<char> op;
map<string,int> mp;
int dfs1(Node* node) {
	int mx = 0;
	for (int i = 0; i < 26; ++i) {
		if (node->links[i]) {
			int cnt = dfs1(node->links[i]) + 1;
			node->best.emplace_back(cnt, i);
			mx = max(mx, cnt);
		}
	}
	sort(node->best.begin(), node->best.end());
	return mx;
}
void dfs2(Node* node) {
	while (node->countEnds--) op.push_back('P');
	for (int i = 0; i < node->best.size(); ++i) {
		op.push_back(node->best[i].second+'a');
		dfs2(node->links[node->best[i].second]);
		op.push_back('-');
	}
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tc=1;
	//cin>>tc;
	while(tc--) {
		int n; cin>>n;
		for(int i=0; i<n; i++) {
			string word; cin>>word;
			trie->insert(word);
		}
		dfs1(trie->root);
		dfs2(trie->root);
		while(op.size() > 0 && op.back() == '-') op.pop_back();
		cout<<op.size()<<'\n';
		for(int i=0; i<op.size(); i++) cout<<op[i]<<'\n';
	}
}

• 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