Submission #1326030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326030		hyyh	Type Printer (IOI08_printer)	C++20	100 / 100	111 ms	99124 KiB

printer

#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <stdio.h>
#include <unordered_map>
#include <bitset>
#include <tuple>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define endl '\n'
#define f first
#define s second

string st;

class Trienode{
public:
    Trienode* child[26];

    bool end;

    int length;

    Trienode(){
        end = false;
        length = 1;
        for(int i{};i < 26;i++){
            child[i] = nullptr;
        }
    }
};

void insert(Trienode* root,string &key){
    Trienode* cur = root;
    vector<Trienode*> path;
    path.emplace_back(root);
    for(auto k:key){
        if(cur->child[k-'a'] == nullptr){
            cur->child[k-'a'] = new Trienode();
        }
        cur = cur->child[k-'a'];
        path.emplace_back(cur);
    }
    cur->end = true;
    for(int i{path.size()-2};i >= 0;i--) path[i]->length = max(path[i]->length,path[i+1]->length+1);
}

void bfs(Trienode* cur){
    if(cur->end){
        st += 'P';
    }
    vector<pii> vc;
    for(int i{};i < 26;i++){
        if(cur->child[i] == nullptr) continue;
        vc.emplace_back(cur->child[i]->length,i);
    }
    sort(vc.begin(),vc.end());
    for(auto [a,b]:vc){
        //cout << a << endl;
        st += 'a'+b;
        bfs(cur->child[b]);
    }
    st += '-';
}

int main(){
    Trienode* root = new Trienode();
    int n;cin >> n;
    for(int i{};i < n;i++){
        string st;cin >> st;
        insert(root,st);
    }
    //cout << "a";
    bfs(root);
    while(st.back() == '-') st.pop_back();
    cout << st.size() << endl;
    for(auto k:st) cout << k << endl;
}

Compilation message (stderr)

printer.cpp: In function 'void insert(Trienode*, std::string&)':
printer.cpp:54:26: warning: narrowing conversion of '(path.std::vector<Trienode*>::size() - 2)' from 'std::vector<Trienode*>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   54 |     for(int i{path.size()-2};i >= 0;i--) path[i]->length = max(path[i]->length,path[i+1]->length+1);
      |               ~~~~~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10