Submission #1248173

#TimeUsernameProblemLanguageResultExecution timeMemory
1248173pastaType Printer (IOI08_printer)C++20
80 / 100
21 ms12104 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back const int maxn = 1e5 + 10; int n, vt = 1; int G[maxn][26], cnt[maxn], dp[maxn], h[maxn], par[maxn]; void add(string s) { int v = 1; for (char c : s) { c -= 'a'; if (!G[v][c]) { G[v][c] = ++vt; par[vt] = v; h[vt] = h[v] + 1; dp[v] = max(dp[v], h[vt]); } v = G[v][c]; } cnt[v]++; while (v != 1) { // cout << v << '\n'; dp[par[v]] = max(dp[par[v]], dp[v]); v = par[v]; } } vector<char> ans; void dfs(int v) { while (cnt[v]--) ans.pb('P'); int mx = 0, id = 0; for (int i = 0; i < 26; i++) { if (!G[v][i]) continue; int u = G[v][i]; if (dp[u] == dp[v] && mx == 0) { mx = u; id = i; continue; } ans.pb(char(i + 'a')); dfs(u); } if (mx > 0) { ans.pb(char(id + 'a')); dfs(mx); } ans.pb('-'); } signed main() { cin >> n; for (int i = 0; i < n; i++) { string s; cin >> s; add(s); } dfs(1); while (ans.back() == '-') ans.pop_back(); cout << ans.size() << '\n'; for (char x : ans) cout << x << '\n'; }
#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...