oj.uz

Submission #939804

# Submission time Handle Problem Language Result Execution time Memory
939804 2024-03-06T19:05:23 Z codefox Type Printer (IOI08_printer) C++14
100 / 100
 102 ms 34380 KB 
#include<bits/stdc++.h>

using namespace std;

#define pii pair<char, int>

vector<vector<pii>> trie;
vector<int> tc;
vector<int> notgo;
vector<char> comm;

void dfs(int i)
{
    pii nogo = {0, -1};
    for (int j = 0; j < tc[i]; j++) comm.push_back('P');
    for (pii ele:trie[i])   
    {
        if (notgo[ele.second]) 
        {
            nogo = ele;
            continue;
        }
        comm.push_back(ele.first);
        dfs(ele.second);
        comm.push_back('-'); 
    }
    if (nogo.second==-1) return;
    comm.push_back(nogo.first);
    dfs(nogo.second);
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n;

    trie.assign(n*20+1, vector<pii>());
    tc.assign(n*20+1, 0);
    notgo.assign(n*20+1, 0);
    int d = 0;

    vector<string> ns(n);
    int longest = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> ns[i];
        if (ns[i].size()>ns[longest].size()) longest = i;
    }

    for (int i =0 ; i < n; i++)
    {
        int curr = 0;
        for (char c:ns[i])
        {
            bool done = 0;
            for (pii ele:trie[curr])
            {
                if (ele.first == c)
                {
                    done = 1;
                    curr = ele.second;
                }
            }
            if (!done)
            {
                trie[curr].push_back({c, ++d});
                curr = d;
            }
            if (longest==i) notgo[curr] = 1;
        }
        tc[curr]++;
    }

    dfs(0);

    cout << comm.size() << "\n";
    for (char c:comm) cout << c << "\n";

    return 0;
}

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 600 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 1 ms 344 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 1 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 1 ms 344 KB Output is correct
2 Correct 1 ms 848 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1200 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3160 KB Output is correct
2 Correct 12 ms 6488 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8752 KB Output is correct
2 Correct 17 ms 9048 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18380 KB Output is correct
2 Correct 79 ms 28788 KB Output is correct
3 Correct 46 ms 23076 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 21252 KB Output is correct
2 Correct 102 ms 34380 KB Output is correct
3 Correct 53 ms 26032 KB Output is correct
4 Correct 79 ms 33476 KB Output is correct