oj.uz

Submission #448040

# Submission time Handle Problem Language Result Execution time Memory
448040 2021-07-28T16:12:13 Z Alex_tz307 Type Printer (IOI08_printer) C++17
0 / 100
 2 ms 204 KB 
#include <bits/stdc++.h>

using namespace std;

ifstream fin("text.in");
ofstream fout("text.out");

struct node {
  int level;
  bool is_end, is_marked;
  node *son[26];

  node() {
    level = is_end = is_marked = 0;
    for (int i = 0; i < 26; ++i)
      son[i] = nullptr;
  }
};

string s;
int longest;
bool found;
vector<char> sol;

void max_self(int &x, int y) {
  x = max(x, y);
}

void Insert(node *nod, int p) {
  max_self(longest, nod->level);
  if (p == (int)s.size()) {
    nod->is_end = true;
    return;
  }
  int nxt = s[p] - 'a';
  if (nod->son[nxt] == nullptr) {
    nod->son[nxt] = new node;
    nod->son[nxt]->level = nod->level + 1;
  }
  Insert(nod->son[nxt], p + 1);
}

bool mark(node *nod) {
  bool is_leaf = true;
  for (int i = 0; i < 26 && is_leaf; ++i)
    if (nod->son[i] != nullptr)
      is_leaf = false;
  if (is_leaf) {
    if (found)
      return false;
    if (nod->level == longest) {
      nod->is_marked = true;
      found = true;
      return true;
    }
    return false;
  }
  bool ok = false;
  for (int i = 0; i < 26 && !ok; ++i)
    if (nod->son[i] != nullptr)
      ok |= mark(nod->son[i]);
  nod->is_marked = ok;
  return ok;
}

void solve(node *nod) {
  if (nod->is_end)
    sol.emplace_back('P');
  bool is_leaf = true;
  for (int i = 0; i < 26; ++i) {
    if (nod->son[i] != nullptr) {
      is_leaf = false;
      if (nod->son[i]->is_marked == false) {
        sol.emplace_back('a' + i);
        solve(nod->son[i]);
        sol.emplace_back('-');
      }
    }
  }
  for (int i = 0; i < 26; ++i) {
    if (nod->son[i] != nullptr && nod->son[i]->is_marked == true) {
      sol.emplace_back('a' + i);
      solve(nod->son[i]);
      break;
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  fin >> n;
  node* root = new node;
  for (int i = 0; i < n; ++i) {
    fin >> s;
    Insert(root, 0);
  }
  mark(root);
  solve(root);
  fout << sol.size() << '\n';
  for (auto it : sol)
    fout << it << '\n';
  return 0;
}

Compilation message

printer.cpp: In function 'void solve(node*)':
printer.cpp:69:8: warning: variable 'is_leaf' set but not used [-Wunused-but-set-variable]
   69 |   bool is_leaf = true;
      |        ^~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -