제출 #1313917

#제출 시각아이디문제언어결과실행 시간메모리
1313917algoproclubType Printer (IOI08_printer)C++20
40 / 100
253 ms79920 KiB
// UUID: 9c9dc833-6750-4697-80c8-cd36b4f8b743
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

vector<vector<int>> t;
vector<char> csak_ide_ne;
vector<bool> veg;
string ans;
int cnt = 0;

void add(string s, bool spec) {
    int cur = 0;
    for (char c : s) {
        if (!t[cur][c-'a']) {
            cnt++;
            t[cur][c-'a'] = cnt;
        }
        if (spec) csak_ide_ne[cur] = c-'a';
        cur = t[cur][c-'a'];
    }
    veg[cur] = true;
}

void dfs(int cur) {
    cerr << cur << "\n";
    if (veg[cur]) ans += 'P';
    for (int i = 0; i < 26; i++) {
        if (csak_ide_ne[cur] == i || t[cur][i] == 0) continue;
        ans += i+'a';
        dfs(t[cur][i]);
        ans += '-';
    }
    int i = csak_ide_ne[cur];
    if (t[cur][i]) {
        ans += i+'a';
        dfs(t[cur][i]);
        ans += '-';
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    vector<string> s(n);
    csak_ide_ne.assign(n*23, 0);
    t.assign(n*23, vector<int>(26));
    veg.resize(n*23, 0);
    int lg = 0;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        lg = max((int) s[i].size(), lg);
    }

    string y;
    for (string x : s) {
        if ((int) x.size() == lg) {
            y = x;
            continue;
        }
        add(x, false);
    }
    
    add(y, true);

    dfs(0);
    while (ans.back() == '-') ans.pop_back();
    cout << ans.size() << "\n";
    for (char c : ans) cout << c << "\n";
	
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...