oj.uz

Submission #1107571

# Submission time Handle Problem Language Result Execution time Memory
1107571 2024-11-01T14:20:00 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 140 ms 103624 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int trie[500002][26], d[500002], mx[500002], id=0, end_[500002];
constexpr int ROOT = 0;
vector<char> ans;

void dfs(int depth = 0, int cur = ROOT) {
	d[cur] = depth;
	mx[cur] = d[cur];
	for (int i = 0; i < 26; i++) {
		if (!trie[cur][i])
			continue;
		dfs(depth + 1, trie[cur][i]);
		mx[cur] = max(mx[cur], mx[trie[cur][i]]);
	}
}   

void dfs_ans(int cur = ROOT) {
	if (end_[cur])
		ans.push_back('P');
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] == mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] != mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	ans.push_back('-');	
}

void add_string(string const & s) {
	int cur = ROOT;
	for (auto & c : s) {
		int x = c - 'a';
		if (trie[cur][x]) {
			cur = trie[cur][x];
		} else {
			cur = trie[cur][x] = ++id;
		}
	}
	end_[cur] = 1;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin >> n;
	string s;
	for (int i = 0; i < n; i++)
		cin >> s, add_string(s);
	dfs(); dfs_ans();
	while(ans.back() != 'P')
		ans.pop_back();
	cout << (int) ans.size() << '\n';
	for (int i = 0; i < (int) ans.size(); i++) 
		cout << ans[i] << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10232 KB Output is correct
2 Correct 21 ms 18512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 20428 KB Output is correct
2 Correct 8 ms 5576 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 42652 KB Output is correct
2 Correct 133 ms 87748 KB Output is correct
3 Correct 75 ms 49096 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35416 KB Output is correct
2 Correct 140 ms 103624 KB Output is correct
3 Correct 79 ms 54472 KB Output is correct
4 Correct 130 ms 97988 KB Output is correct