oj.uz

Submission #70424

# Submission time Handle Problem Language Result Execution time Memory
70424 2018-08-22T20:36:08 Z doowey Type Printer (IOI08_printer) C++14
30 / 100
 246 ms 84616 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double db;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue

struct Node{
  Node *nex[26];
  bool ends;
  int subt;
  Node(){
    for(int i = 0; i < 26;i ++ )
      nex[i] = NULL;
    ends = false;
    subt = 1;
  }
};

Node *Trie = new Node();

vector<char> oper;

int n;
int cnt;

void walk(Node *cur){
  for(int j = 0;j < 26;j ++ ){
    if(cur -> nex[j] != NULL){
      walk(cur -> nex[j]);
      cur -> subt += cur -> nex[j] -> subt;
    }
  }
}

void dfs(Node *cur, bool is_root){
  if(cur -> ends){
    oper.push_back('P');
    cnt ++ ;
  }
  vector<pii> order;
  for(int j = 0;j < 26;j ++ ){
    if(cur -> nex[j] != NULL)
      order.push_back(mp(cur -> nex[j] -> subt, j));
  }
  sort(order.begin(), order.end());
  for(auto x : order){
    if(cur -> nex[x.se] != NULL){
      oper.push_back(char(x.se + 'a'));
      dfs(cur -> nex[x.se], false);
    }
  }
  if(!is_root and cnt != n){
    oper.push_back('-');
  }
}

int main(){
  fastIO;
  cin >> n;
  string a;
  for(int i = 0;i < n;i ++ ){
    cin >> a;
    Node *cur = Trie;
    for(char x : a){
      if(cur -> nex[x - 'a'] == NULL){
        cur -> nex[x - 'a'] = new Node();
      }
      cur = cur -> nex[x - 'a'];
    }
    cur -> ends = true;
  }
  walk(Trie);
  dfs(Trie, true);
  cout << oper.size() << "\n";
  for(auto x : oper)
    cout << x << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 KB Output is correct
2 Correct 2 ms 672 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2152 KB Output is correct
2 Incorrect 10 ms 2780 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 6432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 15304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 37228 KB Output is correct
2 Correct 246 ms 84616 KB Output is correct
3 Incorrect 115 ms 84616 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 84616 KB Output isn't correct
2 Halted 0 ms 0 KB -