Submission #1260178

#TimeUsernameProblemLanguageResultExecution timeMemory
1260178Born_To_LaughType Printer (IOI08_printer)C++17
100 / 100
115 ms60012 KiB
// Born_To_Laugh - Hughie Do #include <bits/stdc++.h> #define alle(AC) AC.begin(), AC.end() using namespace std; typedef long long ll; [[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7; vector<char> ans; string a; struct Prefix_Trie { int n; struct node { int exist = 0; int disttoleaf = 1; int lovchi = 0; array<int, 26> child; }; vector<node> tree; int id = 0; Prefix_Trie(){ tree.push_back(node()); } int newnode(){ id++; tree.push_back(node()); return id; } void insert(string & a){ int pos = 0; for(auto &elm: a){ int val = elm - 'a'; if(!tree[pos].child[val])tree[pos].child[val] = newnode(); pos = tree[pos].child[val]; } tree[pos].exist++; } void distcompute(int pos){ for(int i=0; i<26; ++i){ if(!tree[pos].child[i])continue; distcompute(tree[pos].child[i]); int nxt = tree[pos].child[i]; if(tree[nxt].disttoleaf + 1 > tree[pos].disttoleaf){ tree[pos].lovchi = nxt; tree[pos].disttoleaf = tree[nxt].disttoleaf + 1; } } } void dfs(int pos){ int savesz = a.size(); if(tree[pos].exist){ ans.push_back('P'); } int j = -1; for(int i=0; i<26; ++i){ if(!tree[pos].child[i])continue; int nxt = tree[pos].child[i]; if(nxt == tree[pos].lovchi){ j = i; continue; } a.push_back(char('a' + i)); // cout << a << '\n'; ans.push_back(char('a' + i)); dfs(nxt); while(a.size() != savesz){ a.pop_back(); ans.push_back('-'); } } if(j != -1){ a.push_back(char('a' + j)); ans.push_back(char('a' + j)); dfs(tree[pos].lovchi); } } }; Prefix_Trie trie; void solve(){ int n;cin >> n; for(int i=1; i<=n; ++i){ string a;cin >> a; trie.insert(a); } trie.distcompute(0); trie.dfs(0); cout << ans.size() << '\n'; for(auto &elm: ans)cout << elm << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); 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...