oj.uz

Submission #999898

# Submission time Handle Problem Language Result Execution time Memory
999898 2024-06-16T08:52:05 Z Alfraganus Type Printer (IOI08_printer) C++17
10 / 100
 197 ms 262144 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;

    Trie(vector<str> &s){
        p.push_back({});
        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({});
            index = p[index][x[i]];
        }
    }

    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, 0), cur.pop_back();
        }
    }

    void get(int index, int j){
        if((int)p[index].size() == 0){
            res.push_back('P');
            return;
        }
        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){
            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 << res.size() << endl;
    for(auto x : res)
        cout << x << endl;
}

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 197 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1280 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3340 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 8460 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 23304 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 16384 KB didn't print every word
2 Halted 0 ms 0 KB -