Submission #475751

#	Time	Username	Problem	Language	Result	Execution time	Memory
475751		KhaledFarhat	Type Printer (IOI08_printer)	C++14	100 / 100	132 ms	60464 KiB

printer

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
	TrieNode() : isEnd(false) {
		memset(nextNode, 0, sizeof nextNode);
	}
	
	pair<int, int> farthestLeaf; // {leafDist, edge}
	int nextNode[26];
	bool isEnd;
};

struct Trie {
	Trie() {
		fetchNode();
		root = fetchNode();
	}
	
	void insertWord(const string& s) {
		int current = root;
		int leafDist = s.size();
		
		for (char letter : s) {
			int edge = letter - 'a';
						
			if (nodes[current].nextNode[edge] == 0) {
				int index = fetchNode();
				nodes[current].nextNode[edge] = index;
			}
			
			if (leafDist > nodes[current].farthestLeaf.first) {
				nodes[current].farthestLeaf = {leafDist, edge};
			}
			
			current = nodes[current].nextNode[edge];
		}
		
		nodes[current].isEnd = true;
	}
	
	void getShortestTour(int current = 1, bool shouldErase = false) {		
		if (nodes[current].isEnd == true) {
			operations.push_back('P');
		}
				
		for (int edge = 0; edge < 26; ++edge) {
			int child = nodes[current].nextNode[edge];
			
			if (child != 0 && nodes[current].farthestLeaf.second != edge) {
				operations.push_back((char)('a' + edge));
				getShortestTour(child, true);
			}
		}
		
		if (nodes[current].farthestLeaf.first != 0) {
			operations.push_back((char)('a' + nodes[current].farthestLeaf.second));
			getShortestTour(nodes[current].nextNode[nodes[current].farthestLeaf.second], shouldErase);
		}
		
		if (shouldErase == true) {
			operations.push_back('-');
		}
	}
	
	int fetchNode() {
		nodes.push_back(TrieNode());
		
		return (int)nodes.size() - 1;
	}
	
	int farthestLeaf;
	int root;
	vector<TrieNode> nodes;
	vector<char> operations;
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	Trie trie;
	
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		
		trie.insertWord(s);
	}
	
	trie.getShortestTour();
	
	cout << trie.operations.size() << "\n";
	
	for (char operation : trie.operations) {
		cout << operation << "\n";
	}
	
	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