oj.uz

Submission #881519

# Submission time Handle Problem Language Result Execution time Memory
881519 2023-12-01T11:14:09 Z rxlfd314 Type Printer (IOI08_printer) C++17
20 / 100
 64 ms 44236 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 {
  int dep, mx;
  vt<DS*> ds;
  DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1) {}
  void insert(string s, int i) {
    if (i == size(s))
      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) {
    FOR(i, 0, 25)
      if (ds[i] && (!special || i != mx)) {
        ans.push_back('a' + i);
        ds[i]->dfs2(ans, false);
        ans.push_back('-');
      }
    if (mx < 0)
      ans.push_back('P');
    else if (special) {
      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:17:11: warning: 'DS::ds' will be initialized after [-Wreorder]
   17 |   vt<DS*> ds;
      |           ^~
printer.cpp:16:7: warning:   'int DS::dep' [-Wreorder]
   16 |   int dep, mx;
      |       ^~~
printer.cpp:18:3: warning:   when initialized here [-Wreorder]
   18 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1) {}
      |   ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
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 #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 344 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2280 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 7260 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 17880 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 44236 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 34628 KB didn't print every word
2 Halted 0 ms 0 KB -