oj.uz

Submission #227777

# Submission time Handle Problem Language Result Execution time Memory
227777 2020-04-28T18:01:30 Z FieryPhoenix Type Printer (IOI08_printer) C++11
80 / 100
 1000 ms 60460 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

struct Node{
  int child[26];
  bool end;
  int depth,max_depth;
  Node(){
    for (int i=0;i<26;i++)
      child[i]=0;
    end=false;
    depth=0;
    max_depth=0;
  }
};

vector<Node>trie;

int get_child(int node, int target){
  if (trie[node].child[target]==0){
    trie[node].child[target]=trie.size();
    trie.emplace_back();
  }
  return trie[node].child[target];
}

void add(string s){
  int cur=0;
  vector<int>v;
  for (char c:s){
    int nex=get_child(cur,(int)(c-'a'));
    trie[nex].depth=trie[cur].depth+1;
    trie[nex].max_depth=max(trie[nex].depth,trie[nex].max_depth);
    v.push_back(nex);
    cur=nex;
  }
  trie[cur].end=true;
  cur=0;
  reverse(v.begin(),v.end());
  for (int i=1;i<(int)v.size();i++)
    trie[v[i]].max_depth=max(trie[v[i]].max_depth,trie[v[i-1]].max_depth);
  cout<<endl;
}

vector<char>ans;

void dfs(int node){
  if (trie[node].end)
    ans.push_back('P');
  vector<pair<int,char>>v;
  for (int i=0;i<26;i++)
    if (trie[node].child[i]!=0)
      v.push_back({trie[trie[node].child[i]].max_depth,(char)(i+'a')});
  sort(v.begin(),v.end());
  for (int i=0;i<(int)v.size();i++){
    ans.push_back(v[i].second);
    dfs(trie[node].child[(int)(v[i].second-'a')]);
  }
  ans.push_back('-');
}

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  int N;
  cin>>N;
  trie.emplace_back();
  for (int i=0;i<N;i++){
    string S;
    cin>>S;
    add(S);
  }
  dfs(0);
  while (ans.back()=='-') ans.pop_back();
  cout<<ans.size()<<endl;
  for (char c:ans)
    cout<<c<<endl;
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 22 ms 940 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1456 KB Output is correct
2 Correct 47 ms 2392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 4280 KB Output is correct
2 Correct 249 ms 8052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 8280 KB Output is correct
2 Correct 119 ms 2396 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 30544 KB Output is correct
2 Execution timed out 1089 ms 60460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 16328 KB Output is correct
2 Execution timed out 1100 ms 60456 KB Time limit exceeded
3 Halted 0 ms 0 KB -