oj.uz

답안 #1091976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091976 2024-09-22T18:06:01 Z autoastt Type Printer (IOI08_printer) C++17
40 / 100
 169 ms 150464 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
#define GET_MACRO(_1, _2, _3, _4, NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define rrep(...) GET_MACRO(__VA_ARGS__, rrep3, rrep2, rrep1, rrep0)(__VA_ARGS__)
#define rep0(a) for (int i = 0; i < a; i++)
#define rep1(i, a) for (int i = 0; i < a; i++)
#define rep2(i, a, b) for (int i = a; i <= b; i++)
#define rep3(i, a, b, c) for (int i = a; i <= b; i += c)
#define rrep0(a) for (int i = (a) - 1; i >= 0; i--)
#define rrep1(i, a) for (int i = (a) - 1; i >= 0; i--)
#define rrep2(i, a, b) for (int i = a; i >= b; i--)
#define rrep3(i, a, b, c) for (int i = a; i >= b; i -= c)
#define NL '\n'
 
const bool CASES = false;
const int N = 5e5 + 5;
const int M = 1e9 + 7;
const int INF = 2e9;
const ll LLINF = 1e18;
 
int trie[N][26], nnode, dis[N][26], mxd[N][26];
vi adj[N];
bool stop[N], vis[N];
 
void add(string s) {
    int u = 0;
    for (auto i : s) {
        if (trie[u][i - 'a'] == 0) trie[u][i - 'a'] = ++nnode;
        u = trie[u][i - 'a'];
    }
    stop[u] = true;
}
 
vector<char> ret;
vector<vector<char>> ans(26);
 
void dfs(int u, int now = -1) {
    vis[u] = true;
    if (stop[u]) {
        ans[now].pb('P');
    }
    vector<pii> tmp;
    rep (26) {
        if (mxd[u][i]) tmp.pb({mxd[u][i], i});
    }
    sort(all(tmp));
    for (auto [d, i] : tmp) {
        // cout << u << " " << i << " " << d << NL;
        int v = trie[u][i];
        if (!u) now = i;
        if (!vis[v]) {
            ans[now].pb('a' + i);
            dfs(v, now);
            ans[now].pb('-');
        }
    }
}

int dfs2(int u) {
    int cnt = stop[u];
    rep (26) {
        int v = trie[u][i];
        if (v) {
            dis[u][i] = dfs2(v) + 2;
            mxd[u][i] = *max_element(mxd[v], mxd[v] + 26) + 1;
            cnt += dis[u][i];
        }
    }
    return cnt;
}
 
void solve() {
    int n;
    cin >> n;
    rep (n) {
        string x;
        cin >> x;
        add(x);
    }
    dfs2(0);
    dfs(0);
    sort(all(ans), [](vector<char> a, vector<char> b) {
        while (sz(a) && a.back() == '-') a.pop_back();
        while (sz(b) && b.back() == '-') b.pop_back();
        return sz(a) < sz(b);
    });
    rep (26) {
        rep (j, sz(ans[i])) ret.pb(ans[i][j]);
    }
    while (ret.back() == '-') ret.pop_back();
    cout << sz(ret) << NL;
    for (auto i : ret) cout << i << NL;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if (CASES) cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12096 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 14172 KB Output is correct
2 Incorrect 8 ms 14936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 20056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 32216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 62684 KB Output is correct
2 Correct 146 ms 128456 KB Output is correct
3 Incorrect 77 ms 71628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 51680 KB Output is correct
2 Correct 169 ms 150464 KB Output is correct
3 Incorrect 86 ms 79564 KB Output isn't correct
4 Halted 0 ms 0 KB -