oj.uz

답안 #1000137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000137 2024-06-16T17:29:02 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 907 ms 121380 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long 

const int sz = 5e5 + 5;
const int inf = 1e18;

int trie[sz][26];
int depth[sz];
bool leaf[sz];
int nxt = 0, cnt = 0;
char ch[sz];
vector<int> adj[sz];
vector<char> res;
int n;

struct Trie
{
    void add(string s) 
    {
        int root = 0;
        for(int i = 0; i < s.size(); i++)
        {
            int child = s[i] - 'a';
            if (!trie[root][child]) 
            {
                trie[root][child] = ++nxt;
                adj[root].push_back(trie[root][child]);
                ch[trie[root][child]] = s[i];
            }
            root = trie[root][child];
            depth[root] = max(depth[root], (int)s.size() - i);
        }
        leaf[root] = true;
    }
    void dfs(int node) 
    {
        if (node) res.push_back(ch[node]);
        if (leaf[node]) res.push_back('P'), cnt++;
        for(int to : adj[node]) dfs(to);
        if (cnt != n) res.push_back('-');
    }
};

void solve() 
{
    cin >> n;
    Trie tree;
    for(int i = 1; i <= n; i++) 
    {
        string s;
        cin >> s;
        tree.add(s);
    }
    for(int i = 0; i <= nxt; i++) sort(adj[i].begin(), adj[i].end(), [&](int a, int b)
    {
        return depth[a] < depth[b];
    });
    tree.dfs(0);
    cout << res.size() << endl;
    for(char c : res) cout << c << endl;
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++) solve();
}

Compilation message

printer.cpp: In member function 'void Trie::add(std::string)':
printer.cpp:24:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0; i < s.size(); i++)
      |                        ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 2 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 12152 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 13660 KB Output is correct
2 Correct 24 ms 14172 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 18264 KB Output is correct
2 Correct 115 ms 25436 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 28172 KB Output is correct
2 Correct 42 ms 15448 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 390 ms 52036 KB Output is correct
2 Correct 827 ms 103988 KB Output is correct
3 Correct 434 ms 58996 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 42952 KB Output is correct
2 Correct 907 ms 121380 KB Output is correct
3 Correct 482 ms 65292 KB Output is correct
4 Correct 850 ms 115396 KB Output is correct