Submission #1265764

#TimeUsernameProblemLanguageResultExecution timeMemory
1265764yhx3Type Printer (IOI08_printer)C++20
20 / 100
255 ms29904 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define rep(i,a,b) for (int i = a; i < b; i++) #define rrep(i,a,b) for (int i = a; i >= b; i--) void N() {cout<<"NO\n";} void Y() {cout<<"YES\n";} void isTrue(bool ope) {if (ope) Y();else N();} ll pw(int x,int t) {ll res = 1;while (t--) res *= x;return res;} int lg(int x,int b) {int res = 0;while (x >= b) {x/=b;res++;}return res;} int MD = 1e9+7; ll MX_VL = 1e18; ll MX_ll = 2e9; int BITS = 31; struct Node { char c; vector<int> child; Node(char x) { c = x; rep(i,0,27) child.push_back(-1); } }; void Insert(vector<Node>& trie,string s) { int n = s.length(); int curr = 0; rep(i,0,n) { if (trie[curr].child[s[i]-'a'+1] == -1) { trie[curr].child[s[i]-'a'+1] = trie.size(); trie.push_back(Node(s[i])); } curr = trie[curr].child[s[i]-'a'+1]; } } int countSub(vector<Node>& trie,int ind,vector<int>& cnt) { int mx = 1; rep(i,1,27) { if (trie[ind].child[i] != -1) { mx = max(mx,1+countSub(trie,trie[ind].child[i],cnt)); } } cnt[ind] = mx; return mx; } int lft; vector<char> ans; void printV(vector<Node>& trie,int ind,vector<int>& cnt) { bool ok = false; rep(i,1,27) { if (trie[ind].child[i]!=-1) ok = true; } if (!ok) { ans.push_back('P'); lft--; } rep(i,1,27) { if (trie[ind].child[i]==-1) continue; if (cnt[trie[ind].child[i]]!=(cnt[ind]-1)) { ans.push_back(trie[trie[ind].child[i]].c); printV(trie,trie[ind].child[i],cnt); if (lft > 0) ans.push_back('-'); } } rep(i,1,27) { if (trie[ind].child[i]==-1) continue; if (cnt[trie[ind].child[i]]==(cnt[ind]-1)) { ans.push_back(trie[trie[ind].child[i]].c); printV(trie,trie[ind].child[i],cnt); if (lft > 0) ans.push_back('-'); } } } void solve() { int n; cin>>n; lft = n; vector<Node> trie; char pss = 'd'; trie.push_back(Node(pss)); int mx = 0; rep(i,0,n) { string s; cin>>s; int l = s.length(); mx = max(mx,l); Insert(trie,s); } vector<int> cnt(trie.size(),0); countSub(trie,0,cnt); printV(trie,0,cnt); cout << ans.size() << endl; for (auto c:ans) cout << c << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } }
#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...