Submission #1084624

#TimeUsernameProblemLanguageResultExecution timeMemory
1084624Hamed5001Type Printer (IOI08_printer)C++14
100 / 100
108 ms51664 KiB
#include <bits/stdc++.h> using namespace std; const int K = 26, mxN = 1e6; int trie[mxN][K], cnt[mxN], last; int d[mxN]; void add_string(string const& s) { int v = 0; stack<int> st; for (char ch : s) { st.push(v); int c = ch - 'a'; if (!trie[v][c]) trie[v][c] = ++last; v = trie[v][c]; } cnt[v]++; while (!st.empty()) { v = st.top(); st.pop(); for (int i = 0; i < K; ++i) if (trie[v][i]) d[v] = max(d[v], d[trie[v][i]]+1); } } vector<char> ans; void dfs(int v = 0) { if (cnt[v]) ans.push_back('P'); set<array<int, 3>> st; for (int i = 0; i < K; ++i) { if (trie[v][i]) st.insert({d[trie[v][i]], trie[v][i], i}); } while (!st.empty()) { auto it = *st.begin(); st.erase(st.begin()); ans.push_back('a' + it[2]); dfs(it[1]); ans.push_back('-'); } } int main() { cin.tie(0)->sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; ++i) { string s; cin >> s; add_string(s); } dfs(0); while (!ans.empty() && ans.back() == '-') ans.pop_back(); cout << ans.size() << endl; for (auto it : ans) cout << it << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...