oj.uz

Submission #227778

# Submission time Handle Problem Language Result Execution time Memory
227778 2020-04-28T18:04:48 Z FieryPhoenix Type Printer (IOI08_printer) C++11
100 / 100
 279 ms 60456 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;
  int mx=-1,ind=-1;
  for (int i=0;i<26;i++)
    if (trie[node].child[i]!=0 && trie[trie[node].child[i]].max_depth>mx){
      mx=trie[trie[node].child[i]].max_depth;
      ind=i;
    }
  for (int i=0;i<26;i++){
    if (trie[node].child[i]!=0 && ind!=i){
      ans.push_back((char)(i+'a'));
      dfs(trie[node].child[i]);
    }
  }
  if (ind!=-1){
    ans.push_back((char)(ind+'a'));
    dfs(trie[node].child[ind]);
  }
  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();
  printf("%d\n",ans.size());
  for (char c:ans)
    printf("%c\n",c);
  return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:91:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",ans.size());
                 ~~~~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 256 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 5 ms 512 KB Output is correct
2 Correct 7 ms 940 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4152 KB Output is correct
2 Correct 42 ms 7924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8280 KB Output is correct
2 Correct 48 ms 2268 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 30276 KB Output is correct
2 Correct 231 ms 59944 KB Output is correct
3 Correct 170 ms 30664 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 15816 KB Output is correct
2 Correct 279 ms 59948 KB Output is correct
3 Correct 175 ms 30796 KB Output is correct
4 Correct 251 ms 60456 KB Output is correct