oj.uz

답안 #310572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310572 2020-10-07T11:40:01 Z Temmie Type Printer (IOI08_printer) C++17
80 / 100
 38 ms 28544 KB 
#include <bits/stdc++.h>

int n, ind = 1;
std::vector <char> ans;
std::vector <int> par(1e5);
std::vector <std::vector <int>> tr(1e5, std::vector <int> (26, -1));
std::vector <bool> vis(1e5, false), tak(1e5, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14080 KB Output is correct
2 Correct 13 ms 14080 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 15 ms 14080 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14080 KB Output is correct
2 Correct 14 ms 14080 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14080 KB Output is correct
2 Correct 13 ms 14080 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 14208 KB Output is correct
2 Correct 16 ms 14080 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 14208 KB Output is correct
2 Correct 17 ms 14152 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 14336 KB Output is correct
2 Correct 28 ms 14592 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 14720 KB Output is correct
2 Correct 21 ms 14464 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 28544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 38 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -