oj.uz

Submission #1000020

# Submission time Handle Problem Language Result Execution time Memory
1000020 2024-06-16T13:16:12 Z Alfraganus Type Printer (IOI08_printer) C++17
100 / 100
 125 ms 55220 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define str string
#define endl '\n'
#define all(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x[0] << ' ' << x[1] << endl;

const int mod = 998244353;

int mx = 0;
str cur = "", ans = "";
vector<char> res;

struct Trie{
    
    vector<map<char, int>> p;
    vector<bool> used;

    Trie(vector<str> &s){
        p.push_back({});
        used.push_back(false);
        for(int i = 0; i < (int)s.size(); i ++)
            add(s[i]);
    }

    void add(str &x){
        int index = 0;
        for(int i = 0; i < (int)x.size(); i ++){
            if(p[index][x[i]] == 0)
                p[index][x[i]] = p.size(), p.push_back({}), used.push_back(false);
            index = p[index][x[i]];
        }
        used[index] = true;
    }

    void dfs(int index, int count){
        if((int)p[index].size() == 0){
            if(count > mx){
                mx = count;
                ans = cur;
            }
            return;
        }
        for(auto [c, k] : p[index]){
            cur += c;
            dfs(k, count + 1);
            cur.pop_back();
        }
    }

    void get(int index, int j){
        if(used[index])
            res.push_back('P');
        for(auto [c, k] : p[index]){
            if(j == -1 or ans[j] != c){
                res.push_back(c);
                get(k, -1);
                res.push_back('-');
            }
        }
        if(j != -1 and j < (int)ans.size()){
            res.push_back(ans[j]);
            get(p[index][ans[j]], j + 1);
        }
    }
};

void solve(){
    int n;
    cin >> n;
    vector<str> s(n);
    for(int i = 0; i < n; i ++)
        cin >> s[i];
    Trie t(s);
    t.dfs(0, 0);
    t.get(0, 0);
    cout << (int)res.size() << endl;
    for(auto x : res)
        cout << x << endl;
}

signed main()
{
    fastio;
    int t = 1;
    // cin >> t;
    while(t --)
        solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1172 KB Output is correct
2 Correct 3 ms 1688 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3344 KB Output is correct
2 Correct 14 ms 6924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8204 KB Output is correct
2 Correct 7 ms 2324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 22536 KB Output is correct
2 Correct 96 ms 46564 KB Output is correct
3 Correct 46 ms 26104 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 16120 KB Output is correct
2 Correct 125 ms 55220 KB Output is correct
3 Correct 55 ms 28148 KB Output is correct
4 Correct 84 ms 52200 KB Output is correct