oj.uz

Submission #475751

# Submission time Handle Problem Language Result Execution time Memory
475751 2021-09-24T00:52:33 Z KhaledFarhat Type Printer (IOI08_printer) C++14
100 / 100
 132 ms 60464 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 888 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4224 KB Output is correct
2 Correct 20 ms 7868 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8248 KB Output is correct
2 Correct 7 ms 2340 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 30440 KB Output is correct
2 Correct 116 ms 60300 KB Output is correct
3 Correct 60 ms 30648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15864 KB Output is correct
2 Correct 132 ms 60444 KB Output is correct
3 Correct 65 ms 30644 KB Output is correct
4 Correct 120 ms 60464 KB Output is correct