oj.uz

Submission #727818

# Submission time Handle Problem Language Result Execution time Memory
727818 2023-04-21T11:37:36 Z madtuber Type Printer (IOI08_printer) C++14
100 / 100
 124 ms 51544 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 1 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3280 KB Output is correct
2 Correct 13 ms 6680 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7888 KB Output is correct
2 Correct 7 ms 2004 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 19108 KB Output is correct
2 Correct 100 ms 43452 KB Output is correct
3 Correct 58 ms 22564 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15048 KB Output is correct
2 Correct 124 ms 51544 KB Output is correct
3 Correct 67 ms 25624 KB Output is correct
4 Correct 98 ms 48724 KB Output is correct