oj.uz

Submission #70425

# Submission time Handle Problem Language Result Execution time Memory
70425 2018-08-22T20:43:30 Z doowey Type Printer (IOI08_printer) C++14
100 / 100
 275 ms 100280 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 = max(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 -> subt = a.size();
    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 5 ms 380 KB Output is correct
2 Correct 3 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2248 KB Output is correct
2 Correct 7 ms 2632 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6276 KB Output is correct
2 Correct 37 ms 12920 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15160 KB Output is correct
2 Correct 14 ms 15160 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 37056 KB Output is correct
2 Correct 223 ms 84064 KB Output is correct
3 Correct 131 ms 84064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 84064 KB Output is correct
2 Correct 275 ms 100280 KB Output is correct
3 Correct 153 ms 100280 KB Output is correct
4 Correct 249 ms 100280 KB Output is correct