Submission #673792

#TimeUsernameProblemLanguageResultExecution timeMemory
673792chanhchuong123Type Printer (IOI08_printer)C++14
100 / 100
138 ms76744 KiB
#include <bits/stdc++.h> using namespace std; #define task "C" #define fi first #define se second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } const int MAX = 500000; int n; string s; int dp[MAX]; int numNode; char c[MAX]; int cnt[MAX]; int nxt[MAX][26]; vector<int> adj[MAX]; void add(string s) { int p = 0; for (int i = 0; i < s.size(); ++i) { int LOVE = s[i] - 'a'; if (nxt[p][LOVE] == 0) { c[numNode + 1] = s[i]; nxt[p][LOVE] = ++numNode; adj[p].push_back(numNode); } p = nxt[p][LOVE]; } ++cnt[p]; } void dfs(int u) { for (int v: adj[u]) { dfs(v); maxi(dp[u], dp[v] + 1); } } string res; void re_dfs(int u) { while (cnt[u]--) res += 'P'; for (int v: adj[u]) { res += c[v]; re_dfs(v); } res += '-'; } main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i) { cin >> s; add(s); } dfs(0); for (int i = 0; i <= numNode; ++i) { sort(all(adj[i]), [&](int u, int v) { return dp[u] < dp[v]; }); } re_dfs(0); while (res.back() != 'P') res.pop_back(); cout << res.size() << '\n'; for (char &c: res) cout << c << '\n'; }

Compilation message (stderr)

printer.cpp: In function 'void add(std::string)':
printer.cpp:28:23: 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: At global scope:
printer.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main() {
      | ^~~~
#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...