oj.uz

Submission #963195

# Submission time Handle Problem Language Result Execution time Memory
963195 2024-04-14T17:15:07 Z fzyzzz_z Type Printer (IOI08_printer) C++17
100 / 100
 503 ms 71068 KB 
#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

map<string, int> id; 
int s = 1; 
vector<int> adj[20 * 25000]; 
int bad[20 * 25000]; 
char ch[20 * 25000]; 


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; 
	cin >> n; 
	vector<string> a(n);
	string mx = ""; 
	for (auto & x: a) {
		cin >> x; 
		if (x.size() > mx.size()) mx = x; 
	}

	for (int i = 0; i < 20 * 25000; ++i) bad[i] = 0; 

	for (auto x: a) {
		int at = 0; 
		string cur = ""; 
		for (auto c: x) {
			cur += c; 
			if (id.find(cur) == id.end()) {
				adj[at].push_back(s); 
				id[cur] = s++; 
			}
			at = id[cur]; 
			ch[at] = c; 
			if (x == mx) bad[at] |= 1; 
		}
		bad[at] |= 2; 
		// cout << at << '\n';
	}

	string ans = ""; 

	function<void(int)> dfs = [&] (int x) -> void {
		// cout << "nd " << x << '\n';
		if (x > 0) ans += ch[x]; 
		if (bad[x] & 2) ans += 'P';

		for (auto u: adj[x]) {
			if (!(bad[u] & 1)) {
				dfs(u); 
			}
		}
		for (auto u: adj[x]) {
			if ((bad[u] & 1)) {
				dfs(u); 
			}
		}
		ans += '-'; 
	};
	dfs(0); 

	while (ans.back() == '-') ans.pop_back(); 

	cout << ans.size() << '\n';
	for (auto x: ans) {
		cout << x << '\n';
	}

	return 0; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 4 ms 14428 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 3 ms 14260 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14428 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15192 KB Output is correct
2 Correct 10 ms 15552 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 17496 KB Output is correct
2 Correct 50 ms 21076 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 21920 KB Output is correct
2 Correct 52 ms 16720 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 34036 KB Output is correct
2 Correct 379 ms 61456 KB Output is correct
3 Correct 238 ms 39068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 29168 KB Output is correct
2 Correct 503 ms 71068 KB Output is correct
3 Correct 268 ms 42840 KB Output is correct
4 Correct 409 ms 67340 KB Output is correct