Submission #1236223

#TimeUsernameProblemLanguageResultExecution timeMemory
1236223mazenxvType Printer (IOI08_printer)C++20
100 / 100
105 ms106024 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define all(v) v.begin(), v.end() #define allr(v) v.rbegin(), v.rend() #define F first #define S second #define P push_back #define endl '\n' #define pqmn pi , vector<pi> , greater<pi> const int N = 1e6 + 10; const int R = 5e3 + 10; const int mod = 1e9 + 7; const int inf = 1e9 + 10; const ll infll = 1e17; typedef pair<int, int> pi; typedef vector<int> vi; typedef vector<pi> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; const int CHAR = 26; struct trie { trie* child[CHAR]; int cnt,end , mxlen; trie() { memset(child, 0, sizeof child); cnt = end = 0; mxlen = 0; } void insert(string &str , int i = 0) { cnt++; if (i == (int)str.size()) { end++; mxlen = max(mxlen , i); return; } int cur = str[i]-'a'; if (child[cur] == 0) child[cur] = new trie(); child[cur]->insert(str , i+1); mxlen = max(mxlen , child[cur]->mxlen); } int dfs(vector<char> &ans){ int count = 0; for(int i = 0 ; i < end ; i++){ ans.P('P'); count++; } struct item{ int mx; char c; trie *r; }; vector<item> arr; for(char c = 'a' ; c <= 'z' ; c++){ if(child[c - 'a']){ arr.P({child[c - 'a']->mxlen , c , child[c - 'a']}); } } sort(all(arr) , [](item a , item b){ if(a.mx < b.mx) return true; else return false; }); for(int i = 0 ; i < (int)arr.size() ; i++){ count++; ans.P(arr[i].c); count += arr[i].r->dfs(ans); ans.P('-'); count++; } return count; } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; trie *root = new trie(); for(int i = 0 ; i < n ; i++){ string s; cin >> s; root->insert(s); } vector<char> ans; int k = root->dfs(ans); cout << k - root->mxlen << endl; for(int i = 0 ; i < k - root->mxlen ; i++){ cout << ans[i] << endl; } 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...