oj.uz

답안 #1036378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1036378 2024-07-27T09:58:07 Z stdfloat Type Printer (IOI08_printer) C++17
100 / 100
 121 ms 78216 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = (int)5e5 + 1;

string ans;

vector<bool> vis(N);

vector<int> cnt(N);

vector<vector<int>> E(N, vector<int>(26, -1));

void dfs(int x) {
    while (cnt[x]--) ans += 'P';

    for (int i = 0; i < 26; i++) {
        if (E[x][i] != -1 && !vis[E[x][i]]) {
            ans += 'a' + i;
            dfs(E[x][i]);
        }
    }
    for (int i = 0; i < 26; i++) {
        if (E[x][i] != -1 && vis[E[x][i]]) {
            ans += 'a' + i;
            dfs(E[x][i]);
        }
    }

    if (x) ans += '-';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s(n);
    for (auto &i : s) cin >> i;

    int nm = 1;
    vector<int> d(N), pr(N);
    for (auto i : s) {
        int x = 0;
        for (auto j : i) {
            if (E[x][j - 'a'] == -1) {
                pr[nm] = x;
                d[nm] = d[x] + 1;
                E[x][j - 'a'] = nm++;
            }
        
            x = E[x][j - 'a'];
        }

        cnt[x]++;
    }

    int x = max_element(d.begin(), d.end()) - d.begin();
    while (x) {
        vis[x] = true;
        x = pr[x];
    }

    dfs(0);

    while (ans.back() == '-') ans.pop_back();

    cout << (int)ans.size() << '\n';
    for (auto i : ans) cout << i << '\n';
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 72784 KB Output is correct
2 Correct 39 ms 72848 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 72796 KB Output is correct
2 Correct 39 ms 72788 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 72796 KB Output is correct
2 Correct 44 ms 72784 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 72784 KB Output is correct
2 Correct 38 ms 72912 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 72884 KB Output is correct
2 Correct 46 ms 72784 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 72812 KB Output is correct
2 Correct 46 ms 73044 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 73040 KB Output is correct
2 Correct 56 ms 73552 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 73708 KB Output is correct
2 Correct 55 ms 73552 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 74888 KB Output is correct
2 Correct 90 ms 77168 KB Output is correct
3 Correct 69 ms 76200 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 74736 KB Output is correct
2 Correct 121 ms 78216 KB Output is correct
3 Correct 79 ms 76784 KB Output is correct
4 Correct 92 ms 78000 KB Output is correct