oj.uz

답안 #1077558

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077558 2024-08-27T08:01:23 Z juicy Type Printer (IOI08_printer) C++17
60 / 100
 44 ms 19540 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 25000, L = 20, MAX = N * L + 3, C = 26;

int node;
int dep[MAX], ind[MAX], ma[MAX];
bool flg[N];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 856 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 4 ms 1372 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3292 KB Output is correct
2 Incorrect 19 ms 6744 KB printed invalid word
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 7972 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 19540 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 15188 KB printed invalid word
2 Halted 0 ms 0 KB -