oj.uz

Submission #310574

# Submission time Handle Problem Language Result Execution time Memory
310574 2020-10-07T11:43:20 Z Temmie Type Printer (IOI08_printer) C++17
100 / 100
 167 ms 72300 KB 
#include <bits/stdc++.h>

int n, ind = 1;
std::vector <char> ans;
std::vector <int> par(5e5);
std::vector <std::vector <int>> tr(5e5, std::vector <int> (26, -1));
std::vector <bool> vis(5e5, false), tak(5e5, 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 61 ms 68984 KB Output is correct
2 Correct 60 ms 68984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 68984 KB Output is correct
2 Correct 70 ms 68984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 68984 KB Output is correct
2 Correct 70 ms 68940 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 69016 KB Output is correct
2 Correct 62 ms 68984 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 68984 KB Output is correct
2 Correct 74 ms 68984 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 69072 KB Output is correct
2 Correct 70 ms 69112 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 69240 KB Output is correct
2 Correct 82 ms 69368 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 69624 KB Output is correct
2 Correct 78 ms 69240 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 70132 KB Output is correct
2 Correct 152 ms 71920 KB Output is correct
3 Correct 112 ms 70644 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 70004 KB Output is correct
2 Correct 167 ms 72300 KB Output is correct
3 Correct 120 ms 70900 KB Output is correct
4 Correct 155 ms 72176 KB Output is correct