Submission #872454

#TimeUsernameProblemLanguageResultExecution timeMemory
872454ObadaKhType Printer (IOI08_printer)C++17
90 / 100
1066 ms106424 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; /*-------------------------*/ #define ll long long #define ld long double #define all(v) v.begin(),v.end() #define allr(v) v.rbegin(),v.rend() #define Dracarys ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); template<typename T> using indexed_multiset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef pair<ll, int> pi; const int N = 2e5 + 10; const int infi = 1e9 + 10; const ll infl = 1e18 + 10; const int MOD = 1e9 + 7; const ld eps = 1e-9; string ScanString() { char ch[100000]; scanf("%s", ch); return ch; } vector<char> Ans; const int CHAR = 26; struct TrieNode { TrieNode *child[CHAR]; int Cnt, End, mxval; TrieNode() { memset(child, 0, sizeof child); Cnt = End = mxval = 0; } void add(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0) child[cur] = new TrieNode(); child[cur]->Cnt++; if (i == s.size() - 1) { child[cur]->End++; mxval = s.size(); return; } child[cur]->add(i + 1, s); } void add(string &s) { add(0, s); } void erase(int i, string &s) { int cur = s[i] - 'a'; child[cur]->Cnt--; if (i == s.size() - 1) { child[cur]->End--; return; } child[cur]->erase(i + 1, s); if (!child[cur]->Cnt) { delete child[cur]; child[cur] = 0; } } void erase(string &s) { if (!find(s))return; erase(0, s); } bool find(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0)return 0; if (i == s.size() - 1) { return child[cur]->End > 0; } return child[cur]->find(i + 1, s); } bool find(string &s) { return find(0, s); } int CntPrefix(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0)return 0; if (i == s.size() - 1) { return child[cur]->Cnt; } return child[cur]->CntPrefix(i + 1, s); } int CntPrefix(string &s) { return CntPrefix(0, s); } void DfsMax() { for (int i = 0; i < 26; i++) { if (child[i]) child[i]->DfsMax(), mxval = max(mxval, child[i]->mxval); } } void Dfs() { set<pair<int, int>> st; for (int i = 0; i < 26; i++) if (child[i]) st.insert({child[i]->mxval, i}); for (auto &it: st) { Ans.push_back(char('a' + it.second)); if (child[it.second]->End)Ans.push_back('P'); child[it.second]->Dfs(); Ans.push_back('-'); } } void clear() { for (int i = 0; i < CHAR; i++) if (child[i]) child[i]->clear(), delete child[i], child[i] = 0; } }; void RunTime(int Tc) { int n; cin >> n; TrieNode *Root = new TrieNode(); for (int i = 0; i < n; i++) { string s; cin >> s; Root->add(s); } Root->DfsMax(); Root->Dfs(); while (Ans.back() == '-')Ans.pop_back(); cout << Ans.size() << endl; for (int i = 0; i < Ans.size(); i++) { cout << Ans[i]; if (i != Ans.size() - 1)cout << endl; } } int main() { Dracarys int T = 1; //cin >> T; for (int Tc = 1; Tc <= T; Tc++) { RunTime(Tc); } return 0; }

Compilation message (stderr)

printer.cpp: In member function 'void TrieNode::add(int, std::string&)':
printer.cpp:42:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (i == s.size() - 1) {
      |             ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'void TrieNode::erase(int, std::string&)':
printer.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if (i == s.size() - 1) {
      |             ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'bool TrieNode::find(int, std::string&)':
printer.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if (i == s.size() - 1) {
      |             ~~^~~~~~~~~~~~~~~
printer.cpp: In member function 'int TrieNode::CntPrefix(int, std::string&)':
printer.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (i == s.size() - 1) {
      |             ~~^~~~~~~~~~~~~~~
printer.cpp: In function 'void RunTime(int)':
printer.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0; i < Ans.size(); i++) {
      |                     ~~^~~~~~~~~~~~
printer.cpp:142:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         if (i != Ans.size() - 1)cout << endl;
      |             ~~^~~~~~~~~~~~~~~~~
printer.cpp: In function 'std::string ScanString()':
printer.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%s", ch);
      |     ~~~~~^~~~~~~~~~
#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...