Submission #1249654

#TimeUsernameProblemLanguageResultExecution timeMemory
1249654kaizisntmeType Printer (IOI08_printer)C++20
100 / 100
94 ms55484 KiB
#include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #ifdef LOCAL #include <algo/debug.h> #else #define debug(...) 42 #endif using namespace std; using ll = long long; const int N = 500005; string ch; struct Trie { struct Node { int child[26], h, mx; int exist, cnt; } nodes[N]; vector<char> ans; int cur; Trie() : cur(0) { memset(nodes[0].child, -1, sizeof nodes[0].child); nodes[0].exist = nodes[0].cnt = 0; } int new_node() { cur++; memset(nodes[cur].child, -1, sizeof nodes[cur].child); nodes[cur].exist = nodes[cur].cnt = 0; return cur; } void add(string s) { int pos = 0; for (char x : s) { int c = x - 'a'; if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node(); int npos = nodes[pos].child[c]; nodes[npos].h = nodes[pos].h + 1; pos = npos; nodes[pos].cnt++; } nodes[pos].exist++; } void dfs(int pos) { for (int i = 1; i <= nodes[pos].exist; ++i) ans.eb('P'); for (int c = 0; c < 26; ++c) { if (c == nodes[pos].mx) continue; if (nodes[pos].child[c] == -1) continue; ans.eb(char(c + 'a')); dfs(nodes[pos].child[c]); ans.eb('-'); } int c = nodes[pos].mx; if (c == -1) return; ans.eb(char(c + 'a')); dfs(nodes[pos].child[c]); ans.eb('-'); } int dfs2(int pos) { int mx = 0, k = -1; for (int c = 0; c < 26; ++c) { if (nodes[pos].child[c] == -1) continue; int t = dfs2(nodes[pos].child[c]); if (t > mx) mx = t, k = c; } nodes[pos].mx = k; return max(mx, nodes[pos].h); } }; Trie trie; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int n, mx = 1; string s, cur = ""; cin >> n; vector<char> v; for (int i = 1; i <= n; ++i) { cin >> s; trie.add(s); if (mx < s.size()) mx = s.size(), ch = s; } trie.dfs2(0); trie.dfs(0); vector<char> ans = trie.ans; while (ans.back() == '-') ans.pop_back(); cout << ans.size() << '\n'; for (char x : ans) cout << x << '\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...