oj.uz

Submission #692456

# Submission time Handle Problem Language Result Execution time Memory
692456 2023-02-01T13:02:35 Z Litusiano Type Printer (IOI08_printer) C++14
100 / 100
 243 ms 96608 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
 
//#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define pq priority_queue<ii>
#define mp make_pair
#define ld long double
#define vc vector<char>
#define vvc vector<vc>
#define vb vector<bool>
#define vvb vector<vb>
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
#define endl "\n"
int n;
 
struct Node{
  unordered_map<char,Node*> son;
  bool aca = 0;
};
 
void add(Node* Trie, string& x, int i){
  if(i == x.size()){
    Trie -> aca = 1;
    return;
  }
  if(Trie -> son.find(x[i]) == Trie -> son.end()){
    // creo el Node del Nou caracter,

    Trie-> son[x[i]] = new Node;    
  }
  add(Trie->son[x[i]],x,i+1);
}
int pc = 0;
string mxs = "";
// La ultima paraula es la mes llarga
vc ans;
void dfs1(Node* u, int d, bool MX){
  //cerr<<d<<" "<<mxs.size()<<endl;
  //Processo mxs la ultima, per tant MX es si nomes si es el mxs
  if(u->aca){
    pc++; ans.pb('P');
  }
  bool f = false;
  for(auto x : u->son){
    if(MX && x.f == mxs[d]){
      f = 1;
      continue;
    }
    ans.pb(x.f);
    dfs1(x.s,d+1,0);
    if(pc!=n) ans.pb('-');
  }
  if(MX && f){
    ans.pb(mxs[d]);
    dfs1(u->son[mxs[d]],d+1,1);
    if(pc!=n) ans.pb('-');
  }

}
 
signed main(){
 
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  Node* st = new Node;
  For(i,n,0){
    string x; cin>>x;
    if(x.size() > mxs.size()) mxs = x;
    add(st,x,0);
  }
  // Exploro la Trie
  dfs1(st,0,1);// 1 pq el nul forma part de mxs
  cout<<ans.size()<<endl;
  For(i,ans.size(),0) cout<<ans[i]<<endl;
}

Compilation message

printer.cpp: In function 'void add(Node*, std::string&, int)':
printer.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   if(i == x.size()){
      |      ~~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:23:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 | #define For(i, n, x) for (int i = x; i < n; i++)
......
   88 |   For(i,ans.size(),0) cout<<ans[i]<<endl;
      |       ~~~~~~~~~~~~                      
printer.cpp:88:3: note: in expansion of macro 'For'
   88 |   For(i,ans.size(),0) cout<<ans[i]<<endl;
      |   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5588 KB Output is correct
2 Correct 30 ms 11880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13900 KB Output is correct
2 Correct 15 ms 3284 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 34800 KB Output is correct
2 Correct 194 ms 81232 KB Output is correct
3 Correct 111 ms 40776 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 26292 KB Output is correct
2 Correct 243 ms 96608 KB Output is correct
3 Correct 125 ms 46240 KB Output is correct
4 Correct 209 ms 91096 KB Output is correct