Submission #900666

#TimeUsernameProblemLanguageResultExecution timeMemory
900666vaneaType Printer (IOI08_printer)C++14
100 / 100
87 ms48036 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 5e5+10; int trie[mxN][26]; bool stop[mxN], marked[mxN]; int cnt = 0; string alpha = "abcdefghijklmnopqrstuvwxyz"; void insert(string s) { int node = 0; for(auto c : s) { if(trie[node][c-'a'] == 0) trie[node][c-'a'] = ++cnt; node = trie[node][c-'a']; } stop[node] = true; } void mark(string s) { int node = 0; for(auto c : s) { marked[trie[node][c-'a']] = true; node = trie[node][c-'a']; } } vector<char> ans; void dfs(int node) { if(stop[node]) ans.push_back('P'); vector<pair<int, char>> later; for(auto c : alpha) { int k = trie[node][c-'a']; if(k && marked[k]) later.push_back({k, c}); else if(k) { ans.push_back(c); dfs(k); ans.push_back('-'); } } for(auto it : later) { ans.push_back(it.second); dfs(it.first); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string lng = ""; for(int i = 0; i < n; i++) { string s; cin >> s; insert(s); if(s.length() > lng.length()) lng = s; } mark(lng); dfs(0); cout << ans.size() << '\n'; 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...