Submission #1265766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265766		yhx3	Type Printer (IOI08_printer)	C++20	30 / 100	258 ms	31152 KiB

printer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rrep(i,a,b) for (int i = a; i >= b; i--)
void N() {cout<<"NO\n";}
void Y() {cout<<"YES\n";}
void isTrue(bool ope) {if (ope) Y();else N();}
ll pw(int x,int t) {ll res = 1;while (t--) res *= x;return res;}
int lg(int x,int b) {int res = 0;while (x >= b) {x/=b;res++;}return res;}
int MD = 1e9+7;
ll MX_VL = 1e18;
ll MX_ll = 2e9;
int BITS = 31;

struct Node {
    char c;
    vector<int> child;
    bool prnt;
    Node(char x,bool p) {
        c = x;
        rep(i,0,27) child.push_back(-1);
        prnt = p;
    }
};

void Insert(vector<Node>& trie,string s) {
    int n = s.length();
    int curr = 0;
    rep(i,0,n) {
        if (trie[curr].child[s[i]-'a'+1] == -1) {
            trie[curr].child[s[i]-'a'+1] = trie.size();
            trie.push_back(Node(s[i],i == (n-1)));
        }
        curr = trie[curr].child[s[i]-'a'+1];
    }
}

int countSub(vector<Node>& trie,int ind,vector<int>& cnt) {
    int mx = 1;
    rep(i,1,27) {
        if (trie[ind].child[i] != -1) {
            mx = max(mx,1+countSub(trie,trie[ind].child[i],cnt));
        }
    }
    cnt[ind] = mx;
    return mx;
}

int lft;
vector<char> ans;

void printV(vector<Node>& trie,int ind,vector<int>& cnt) {
    if (ind!=0) ans.push_back(trie[ind].c);
    if (trie[ind].prnt) {
        ans.push_back('P');
        lft--;
    }
    rep(i,1,27) {
        if (trie[ind].child[i]==-1) continue;
        if (cnt[trie[ind].child[i]]!=(cnt[ind]-1)) {
            printV(trie,trie[ind].child[i],cnt);
        }
    }
    rep(i,1,27) {
        if (trie[ind].child[i]==-1) continue;
        if (cnt[trie[ind].child[i]]==(cnt[ind]-1)) {
            printV(trie,trie[ind].child[i],cnt);
        }
    }
    if (lft > 0) ans.push_back('-');
}

void solve() {
    int n;
    cin>>n;
    lft = n;
    vector<Node> trie;
    char pss = 'd';
    trie.push_back(Node(pss,false));
    int mx = 0;
    rep(i,0,n) {
        string s;
        cin>>s;
        int l = s.length();
        mx = max(mx,l);
        Insert(trie,s);
    }
    vector<int> cnt(trie.size(),0);
    countSub(trie,0,cnt);
    printV(trie,0,cnt);
    cout << ans.size() << endl;
    for (auto c:ans) cout << c << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 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