Submission #1197565

#TimeUsernameProblemLanguageResultExecution timeMemory
1197565zyadhanyType Printer (IOI08_printer)C++20
100 / 100
96 ms62064 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll long long #define ld long double #define pl pair<ll, ll> #define vi vector<long long> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "-1\n"; return;} using namespace std; class Trie { public: struct trie_node { ll cnt; ll mx; int next[26]; trie_node() { cnt = mx = 0; memset(next, -1, sizeof(next)); } }; ll get(string &res) {return (get(0, res));} void add(string &s) {add(0, s, 0, 0);} Trie() {tree.resize(1, trie_node());} private: vector<trie_node> tree; ll get(ll m, string &res) { for (int i = 0; i < tree[m].cnt; i++) { res += "P"; } for (int i = 0; i < 26; i++) { if (tree[m].next[i] != -1 && tree[tree[m].next[i]].mx != tree[m].mx) { res += (char) 'a'+i; get(tree[m].next[i], res); res += '-'; } } for (int i = 0; i < 26; i++) { if (tree[m].next[i] != -1 && tree[tree[m].next[i]].mx == tree[m].mx) { res += (char) 'a'+i; get(tree[m].next[i], res); res += '-'; } } return 0; } void add(ll m, string &s, ll h, ll idx) { tree[m].mx = max(tree[m].mx, h); if (!s[idx]) { tree[m].cnt++; return; } int nxt = s[idx] - 'a'; if (tree[m].next[nxt] == -1) { tree[m].next[nxt] = tree.size(); tree.push_back(trie_node()); } add(tree[m].next[nxt], s, h+1,idx + 1); tree[m].mx = max(tree[m].mx, tree[tree[m].next[nxt]].mx); } }; const int MODE = 1e9+7; void solve(int tc) { ll n; cin >> n; Trie tr; for (int i = 0; i < n; i++) { string s; cin >> s; tr.add(s); } string res = ""; tr.get(res); while (res.back() == '-') { res.pop_back(); } cout << res.size() << '\n'; for (auto c : res) cout << c << '\n'; } signed main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; // freopen("dec.in", "r", stdin); // freopen("dec.out", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }
#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...