Submission #727818

#	Time	Username	Problem	Language	Result	Execution time	Memory
727818		madtuber	Type Printer (IOI08_printer)	C++14	100 / 100	124 ms	51544 KiB

printer

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define fir first
#define sec second
#define sz(x) x.size()
#define pb push_back
 
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using pdb = pair<double,double>;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using ull = unsigned long long;
const double EPS = (1e-6);
 
void setio(string s){
    freopen((s + ".in").c_str(),"r",stdin);
    freopen((s + ".out").c_str(),"w",stdout);
}

struct Trie{
    map<char, Trie> c;
    bool mark = false;
    int len = 1;

    void insert(string& s, int pos){
        if (pos != sz(s)) c[s[pos]].insert(s, pos+1);
        else mark = true;
    }

    int dfs(){
        int mx = 0;
        for(auto& i : c){
            mx = max(mx, i.sec.dfs());
        } 
        len += mx;
        return len;
    }

    void dfs2(bool good, vector<char>& res){
        if (mark) res.pb('P');
        pi bst = {-1, 0};
        if (good){
            for(auto& i : c){
                bst =max(bst, {i.sec.len, i.fir}); 
            }
        }

        for(auto& i : c){
            if (i.fir != bst.sec){
                res.pb(i.fir);
                i.sec.dfs2(0, res);
            }
        }
        if (bst.fir != -1){
            res.pb(bst.sec);
            c[bst.sec].dfs2(1, res);
        }
        if (!good) res.pb('-');
    }
    
};

void solve(){
    int n;
    cin >> n;

    Trie tr;

    for(int i{}; i < n; i++){
        string s;
        cin >> s;
        tr.insert(s, 0);
    }

    vector<char> res;

    tr.dfs();
    tr.dfs2(1, res);
    cout << sz(res) << '\n';
    for(auto& i :res) cout << i << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

printer.cpp: In member function 'void Trie::insert(std::string&, int)':
printer.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if (pos != sz(s)) c[s[pos]].insert(s, pos+1);
      |                 ^
printer.cpp: In function 'void setio(std::string)':
printer.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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