Submission #1313891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313891		algoproclub	Type Printer (IOI08_printer)	C++20	100 / 100	122 ms	99104 KiB

printer

// UUID: 2350ce0e-9b90-4788-a2a0-3d302c20e3fd
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define srt(x) x.begin(),x.end()
const int INF = 500001;

int t[INF][26];
int veg[INF];
int maxlen[INF];
int cnt = 1;
string ans = "";
int vegcnt = 0;

void update(string &s, int x, int i)
{
    char c = s[i];
    if(t[x][c-97] == 0)
    {
        t[x][c-97] = ++cnt;
        maxlen[cnt] = 1;
    }
    x = t[x][c-97];
    if(i < s.size()-1)
    {
        update(s, x, ++i);
        for(int j = 0; j < 26; j++) maxlen[x] = max(maxlen[x], maxlen[t[x][j]] + 1);
    }
    else
    {
        if(veg[x] == 0) vegcnt++;
        veg[x] += 1;
    }
}

void solve(int x)
{
    if(veg[x] > 0)
    {
        while(veg[x]--) ans += "P";
        vegcnt--;
    }
    vector<pii>v;
    for(int i = 0; i < 26; i++)
    {
        if(t[x][i] > 0) v.pb({maxlen[t[x][i]], i});
    }
    sort(srt(v));
    for(auto[len, i] : v)
    {
        ans += char(i+97);
        solve(t[x][i]);
        if(vegcnt > 0) ans += "-";
    }
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
	int n; cin >> n;
    while(n--)
    {
        string s; cin >> s;
        update(s, 1, 0);
    }
    solve(1);
    cout << ans.size() << "\n";
    for(char c : ans) cout << c << "\n";
}

• 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