oj.uz

Submission #881522

# Submission time Handle Problem Language Result Execution time Memory
881522 2023-12-01T11:21:24 Z rxlfd314 Type Printer (IOI08_printer) C++17
100 / 100
 195 ms 119964 KB 
#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = max(1ll * a, 1ll * (b)))
#define chmin(a, b) (a = min(1ll * a, 1ll * (b)))

struct DS {
  bool yes;
  int dep, mx;
  vt<DS*> ds;
  DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
  void insert(string &s, int i) {
    if (i == size(s)) {
      yes = true;
      return;
    }
    if (!ds[s[i]-'a'])
      ds[s[i]-'a'] = new DS(dep+1);
    ds[s[i]-'a']->insert(s, i+1);
  }
  void dfs1() {
    FOR(i, 0, 25)
      if (ds[i]) {
        ds[i]->dfs1();
        if (ds[i]->dep > dep)
          dep = ds[i]->dep, mx = i;
      }
  }
  void dfs2(vt<char> &ans, bool special) {
    if (yes)
      ans.push_back('P');
    FOR(i, 0, 25)
      if (ds[i] && (!special || i != mx)) {
        ans.push_back('a' + i);
        ds[i]->dfs2(ans, false);
        ans.push_back('-');
      }
    if (special && ~mx) {
      ans.push_back('a' + mx);
      ds[mx]->dfs2(ans, true);
    }
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  DS *ds = new DS(0);
  FOR(_, 1, N) {
    string s;
    cin >> s;
    ds->insert(s, 0);
  }
  vt<char> ans;
  ds->dfs1();
  ds->dfs2(ans, true);
  cout << size(ans) << '\n';
  for (char c : ans)
    cout << c << '\n';
}

Compilation message

printer.cpp: In constructor 'DS::DS(int)':
printer.cpp:18:11: warning: 'DS::ds' will be initialized after [-Wreorder]
   18 |   vt<DS*> ds;
      |           ^~
printer.cpp:17:7: warning:   'int DS::dep' [-Wreorder]
   17 |   int dep, mx;
      |       ^~~
printer.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
      |   ^~
printer.cpp:17:12: warning: 'DS::mx' will be initialized after [-Wreorder]
   17 |   int dep, mx;
      |            ^~
printer.cpp:16:8: warning:   'bool DS::yes' [-Wreorder]
   16 |   bool yes;
      |        ^~~
printer.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
      |   ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2140 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7260 KB Output is correct
2 Correct 19 ms 15196 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17784 KB Output is correct
2 Correct 7 ms 3932 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 44096 KB Output is correct
2 Correct 139 ms 101060 KB Output is correct
3 Correct 80 ms 52176 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34420 KB Output is correct
2 Correct 195 ms 119964 KB Output is correct
3 Correct 87 ms 59084 KB Output is correct
4 Correct 136 ms 113352 KB Output is correct