Submission #415998

#TimeUsernameProblemLanguageResultExecution timeMemory
415998fvogel499Type Printer (IOI08_printer)C++14
0 / 100
52 ms48276 KiB
/* File created on 06/01/2021 at 20:53:10. Link to problem: https://oj.uz/problem/view/IOI08_printer Description: use a trie structures Time complexity: O(N) Space complexity: O(N) Status: DEV Copyright: Ⓒ 2021 Francois Vogel */ #include <iostream> #include <cmath> #include <vector> #include <bitset> #include <queue> #include <cstring> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <algorithm> using namespace std; #define pii pair<int, int> #define f first // #define s second #define pb push_back #define ins insert #define cls clear #define ll long long vector<char> steps; int proc; struct Node { Node(char lt, int ld) { t = lt; d = ld; md = d; mn = nullptr; words = 0; for (int i = 0; i < 26; i++) exist[i] = nullptr; } void add(string& s, int k) { if (k == s.size()) { words++; return; } int i = s[k]-'a'; if (exist[i] == nullptr) { exist[i] = new Node(char(i)+'a', d+1); c.pb(exist[i]); } exist[i]->add(s, k+1); if (exist[i]->md > md) { md = exist[i]->md; mn = exist[i]; } } int words, d, md; char t; Node* exist [26]; vector<Node*> c; Node* mn; }; void dfs(Node* i) { for (int j = 0; j < i->words; j++) { steps.pb('P'); proc--; } for (Node* j : i->c) { if (j != i->mn) { steps.pb(j->t); dfs(j); steps.pb('-'); } } if (i->mn == nullptr) return; steps.pb(i->mn->t); dfs(i->mn); if (proc != 0) steps.pb('-'); } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); Node* root = new Node('$', 0); int n; cin >> n; string ls; for (int i = 0; i < n; i++) { cin >> ls; root->add(ls, 0); } proc = n; dfs(root); cout << steps.size() << endl; // for (char i : steps) cout << i << endl; int d = 0; d++; }

Compilation message (stderr)

printer.cpp: In member function 'void Node::add(std::string&, int)':
printer.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         if (k == s.size()) {
      |             ~~^~~~~~~~~~~
#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...