oj.uz

Submission #1000014

# Submission time Handle Problem Language Result Execution time Memory
1000014 2024-06-16T13:05:32 Z Alfraganus Type Printer (IOI08_printer) C++17
70 / 100
 100 ms 47080 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;
        }
        else if((int)p[index].size() == 1){
            for(auto [c, k] : p[index]){
                cur += c;
                dfs(k, count + 1);
                cur.pop_back();
            }
        }
        else{
            for(auto [c, k] : p[index])
                cur += c, dfs(k, 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 344 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 1 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 0 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 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8456 KB Output is correct
2 Correct 7 ms 2580 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 22280 KB Output is correct
2 Correct 100 ms 47080 KB Output is correct
3 Correct 48 ms 24984 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 16188 KB Output isn't correct
2 Halted 0 ms 0 KB -