Submission #999897

#	Time	Username	Problem	Language	Result	Execution time	Memory
999897		Alfraganus	Type Printer (IOI08_printer)	C++17	0 / 100	57 ms	23540 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define endl '\n'
#define all(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x[0] << ' ' << x[1] << endl;

const int mod = 998244353;

int mx = 0;
str cur = "", ans = "";
vector<char> res;

struct Trie{
    
    vector<map<char, int>> p;

    Trie(vector<str> &s){
        p.push_back({});
        for(int i = 0; i < (int)s.size(); i ++)
            add(s[i]);
    }

    void add(str &x){
        int index = 0;
        for(int i = 0; i < (int)x.size(); i ++){
            if(p[index][x[i]] == 0)
                p[index][x[i]] = p.size(), p.push_back({});
            index = p[index][x[i]];
        }
    }

    void dfs(int index, int count){
        if((int)p[index].size() == 0){
            if(count > mx){
                mx = count;
                ans = cur;
            }
            return;
        }
        else if((int)p[index].size() == 1){
            for(auto [c, k] : p[index]){
                cur += c;
                dfs(k, count + 1);
                cur.pop_back();
            }
        }
        else{
            for(auto [c, k] : p[index])
                cur += c, dfs(k, 0), cur.pop_back();
        }
    }

    void get(int index, int j){
        cout << index << ' ' << j << endl;
        if((int)p[index].size() == 0){
            res.push_back('P');
            return;
        }
        for(auto [c, k] : p[index]){
            if(j == -1 or ans[j] != c){
                res.push_back(c);
                get(k, -1);
                res.push_back('-');
            }
        }
        if(j != -1){
            res.push_back(ans[j]);
            get(p[index][ans[j]], j + 1);
        }
    }
};

void solve(){
    int n;
    cin >> n;
    vector<str> s(n);
    for(int i = 0; i < n; i ++)
        cin >> s[i];
    Trie t(s);
    t.dfs(0, 0);
    cout << mx << ' ' << ans << endl;
    t.get(0, 0);
    cout << res.size() << endl;
    for(auto x : res)
        cout << x << endl;
}

signed main()
{
    fastio;
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
        cout << endl;        
    }
}

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