제출 #1126239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126239		isa	Type Printer (IOI08_printer)	C++20	0 / 100	140 ms	79076 KiB

printer

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl "\n"
#define ff first
#define ss second
#define input(x) for (auto &it : x) cin >> it;
#define output(x) for (auto &it : x) cout << it << ' ';
#define sws std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int INF = 0x3f3f3f3f3f;
const long double PI = acos(-1);
const int MAX = 1e3 + 5;
const int MOD = 1e9 + 7;

const vector<int> new_node = vector<int>(26, -1);
class Trie
{
    public:
        vector<vector<int>> adj;
        vector<int> max_depth;
        vector<bool> str_ends;

        Trie()
        {
            adj.pb(new_node);
            str_ends.pb(false);
        }

        void add_str(string &s)
        {
            int idx = 0, no = 0;

            while (idx < s.size())
            {
                if (adj[no][s[idx] - 'a'] != -1) no = adj[no][s[idx] - 'a'];
                else
                {
                    adj[no][s[idx] - 'a'] = adj.size();
                    no = adj.size();
                    adj.pb(new_node);
                    str_ends.pb(false);
                }

                idx++;
            }

            str_ends[no] = true;
        }

        void process_depth()
        {
            max_depth = vector<int>(adj.size(), 0);
            vector<vector<int>> depth(adj.size(), new_node);

            for(int no = adj.size()-1; no >= 0; no--)
            {
                int mai = 0;
                for(int i = 0;i < 26; i++)
                {
                    if (adj[no][i] == -1) depth[no][i] = 0;
                    else depth[no][i] = 1 + max_depth[adj[no][i]]; 

                    mai = max(mai, depth[no][i]);
                }

                max_depth[no] = mai;
            }
        }
};

Trie T;
int n;
vector<char> ans;
void dfs(int node)
{
    cout << "stuck" << ' ' << node << endl;
    if(T.str_ends[node])
    {
        ans.pb('P');
    }
    for(int i = 0; i < 26; i++)
    {
        if(T.adj[node][i] == -1 || (T.max_depth[T.adj[node][i]] == T.max_depth[node]-1)) continue;
        ans.pb('a'+i);
        dfs(T.adj[node][i]);
    }

    for(int i = 0; i < 26; i++)
    {
        if(T.adj[node][i] == -1)continue;
        if(T.max_depth[T.adj[node][i]] != T.max_depth[node]-1) continue;
        ans.pb('a'+i);
        dfs(T.adj[node][i]);
    }
    ans.pb('-');
    return;
}
void solve()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        T.add_str(s);
    }
    T.process_depth();
    dfs(0);

    int aux = ans.size()-1;
    int cnt = aux - T.max_depth[0];
    cout << cnt << '\n';
    for(int i = 0; i < cnt; i++)cout << ans[i] << '\n';
    return;
}
int32_t main()
{   sws

    int t;
    t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

• 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