# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
727818 | 2023-04-21T11:37:36 Z | madtuber | Type Printer (IOI08_printer) | C++14 | 124 ms | 51544 KB |
#include <bits/stdc++.h> #define all(x) begin(x),end(x) #define fir first #define sec second #define sz(x) x.size() #define pb push_back using namespace std; using ll = long long; using vi = vector<int>; using pi = pair<int,int>; using pdb = pair<double,double>; using pll = pair<ll,ll>; using vll = vector<ll>; using ull = unsigned long long; const double EPS = (1e-6); void setio(string s){ freopen((s + ".in").c_str(),"r",stdin); freopen((s + ".out").c_str(),"w",stdout); } struct Trie{ map<char, Trie> c; bool mark = false; int len = 1; void insert(string& s, int pos){ if (pos != sz(s)) c[s[pos]].insert(s, pos+1); else mark = true; } int dfs(){ int mx = 0; for(auto& i : c){ mx = max(mx, i.sec.dfs()); } len += mx; return len; } void dfs2(bool good, vector<char>& res){ if (mark) res.pb('P'); pi bst = {-1, 0}; if (good){ for(auto& i : c){ bst =max(bst, {i.sec.len, i.fir}); } } for(auto& i : c){ if (i.fir != bst.sec){ res.pb(i.fir); i.sec.dfs2(0, res); } } if (bst.fir != -1){ res.pb(bst.sec); c[bst.sec].dfs2(1, res); } if (!good) res.pb('-'); } }; void solve(){ int n; cin >> n; Trie tr; for(int i{}; i < n; i++){ string s; cin >> s; tr.insert(s, 0); } vector<char> res; tr.dfs(); tr.dfs2(1, res); cout << sz(res) << '\n'; for(auto& i :res) cout << i << '\n'; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; while(t--){ solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 320 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1108 KB | Output is correct |
2 | Correct | 2 ms | 1236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 3280 KB | Output is correct |
2 | Correct | 13 ms | 6680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 7888 KB | Output is correct |
2 | Correct | 7 ms | 2004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 19108 KB | Output is correct |
2 | Correct | 100 ms | 43452 KB | Output is correct |
3 | Correct | 58 ms | 22564 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 44 ms | 15048 KB | Output is correct |
2 | Correct | 124 ms | 51544 KB | Output is correct |
3 | Correct | 67 ms | 25624 KB | Output is correct |
4 | Correct | 98 ms | 48724 KB | Output is correct |