oj.uz

Submission #1077565

# Submission time Handle Problem Language Result Execution time Memory
1077565 2024-08-27T08:02:43 Z juicy Type Printer (IOI08_printer) C++17
100 / 100
 94 ms 52816 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int MAX = 500005, C = 26;

int node;
int dep[MAX], ind[MAX], ma[MAX];
bool flg[MAX];
array<int, C> nxt[MAX];

void add(string s) {
  int p = 0;
  for (char c : s) {
    if (!nxt[p][c - 'a']) {
      nxt[p][c - 'a'] = ++node;
    }
    p = nxt[p][c - 'a'];
  }
  flg[p] = 1;
}

void dfs(int u) {
  ma[u] = dep[u];
  ind[u] = u;
  for (int v : nxt[u]) {
    if (v) {
      dep[v] = dep[u] + 1;
      dfs(v);
      if (ma[v] > ma[u]) {
        ma[u] = ma[v];
        ind[u] = v;
      }
    }
  }
}

void dfs(int u, bool keep) {
  if (flg[u]) {
    cout << "P" << "\n";
  }
  char s;
  for (int i = 0; i < C; ++i) {
    int v = nxt[u][i];
    if (v && v != ind[u]) {
      cout << char(i + 'a') << "\n";
      dfs(v, 0);
    } else if (v == ind[u]) {
      s = i + 'a';
    }
  }
  if (ind[u] ^ u) {
    cout << s << "\n";
    dfs(ind[u], keep);
  }
  if (!keep) {
    cout << "-" << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    string s; cin >> s;
    add(s);
  }
  dfs(0);
  cout << 2 * node + n - ma[0] << "\n";
  dfs(0, 1);
  return 0;
}

Compilation message

printer.cpp: In function 'void dfs(int, bool)':
printer.cpp:48:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   char s;
      |        ^

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 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 348 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 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3416 KB Output is correct
2 Correct 19 ms 6748 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8024 KB Output is correct
2 Correct 5 ms 2140 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 19540 KB Output is correct
2 Correct 81 ms 44368 KB Output is correct
3 Correct 51 ms 23168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15448 KB Output is correct
2 Correct 94 ms 52816 KB Output is correct
3 Correct 45 ms 26188 KB Output is correct
4 Correct 82 ms 49744 KB Output is correct