oj.uz

Submission #310573

# Submission time Handle Problem Language Result Execution time Memory
310573 2020-10-07T11:41:26 Z Temmie Type Printer (IOI08_printer) C++17
60 / 100
 11 ms 8832 KB 
#include <bits/stdc++.h>

int n, ind = 1;
std::vector <char> ans;
std::vector <int> par(3e4);
std::vector <std::vector <int>> tr(3e4, std::vector <int> (26, -1));
std::vector <bool> vis(3e4, false), tak(3e4, false);

int add(const std::string& s) {
	int r = 0;
	for (const char& c : s) {
		if (tr[r][c - 'a'] == -1) tr[r][c - 'a'] = ind, par[ind++] = r;
		r = tr[r][c - 'a'];
	}
	vis[r] = true;
	return r;
}

void dfs(int now = 0) {
	if (vis[now]) ans.push_back('P');
	char ch;
	int other = -1;
	for (int i = 0; i < 26; i++) {
		if (tr[now][i] == -1) continue;
		char c = i + 'a';
		if (tak[tr[now][i]]) ch = c, other = tr[now][i];
		else ans.push_back(c), dfs(tr[now][i]), ans.push_back('-');
	}
	if (other != -1) ans.push_back(ch), dfs(other);
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n;
	int l = 0, node = -1;
	par[0] = -1;
	for (int i = 0; i < n; i++) {
		std::string s; std::cin >> s;
		int now = add(s);
		if ((int)s.length() > l) l = s.length(), node = now;
	}
	while ((node) >= 0) tak[node] = true, node = par[node];
	dfs();
	std::cout << ans.size() << "\n";
	for (char c : ans) std::cout << c << "\n";
	
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 5 ms 4480 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 5 ms 4480 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4480 KB Output is correct
2 Correct 5 ms 4480 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4480 KB Output is correct
2 Correct 7 ms 4608 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4608 KB Output is correct
2 Runtime error 11 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -