Submission #858946

#TimeUsernameProblemLanguageResultExecution timeMemory
858946ntkphongType Printer (IOI08_printer)C++14
70 / 100
119 ms57528 KiB
#include <bits/stdc++.h> using namespace std; struct node { int w_count; int child[26]; }; int n; vector<node> tree; vector<int> h, mark; vector<char> answer; int id_max; void new_node() { node x; x.w_count = 0; for(int i = 0; i < 26; i ++) x.child[i] = -1; tree.push_back(x); } void init() { new_node(); } void add(string s) { int idx = 0; for(int i = 0; i < s.size(); i ++) { int w = s[i] - 'a'; if(tree[idx].child[w] == -1) { new_node(); tree[idx].child[w] = tree.size() - 1; } idx = tree[idx].child[w]; } tree[idx].w_count ++ ; } void dfs(int u, int par) { vector<int> g; for(int i = 0; i < 26; i ++) { int v = tree[u].child[i]; if(v == -1) continue ; g.push_back(v); } if(g.size() > 1) { h[u] = 0; } if(g.size() == 0 || g.size() == 1) { h[u] = max(1, h[par] + 1); } if(g.size() == 0) { if(h[u] > h[id_max]) { id_max = u; } } for(int v : g) { dfs(v, u); } } void DFS(int u) { if(u == id_max) { mark[u] = 1; return ; } for(int i = 0; i < 26; i ++) { int v = tree[u].child[i]; if(v == -1) continue ; DFS(v); mark[u] = (mark[u] || mark[v]); } } void _dfs(int u) { for(int i = 1; i <= tree[u].w_count; i ++) answer.push_back('P'); if(u == id_max) { cout << answer.size() << "\n"; for(auto c : answer) cout << c << "\n"; exit(0); } for(int i = 0; i < 26; i ++) { int v = tree[u].child[i]; if(v == -1) continue ; if(!mark[v]) { answer.push_back((char)(i + 'a')); _dfs(v); answer.push_back('-'); } } for(int i = 0; i < 26; i ++) { int v = tree[u].child[i]; if(v == -1) continue ; if(mark[v]) { answer.push_back((char)(i + 'a')); _dfs(v); answer.push_back('-'); } } } int main() { #define taskname "" if(fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } cin.tie(0)->sync_with_stdio(0); cin >> n; init(); for(int i = 1; i <= n; i ++) { string s; cin >> s; add(s); } h.resize(tree.size()); mark.resize(tree.size()); dfs(0, 0); DFS(0); _dfs(0); return 0; }

Compilation message (stderr)

printer.cpp: In function 'void add(std::string)':
printer.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < s.size(); i ++) {
      |                    ~~^~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...