Submission #1164835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164835		jadai007	Type Printer (IOI08_printer)	C++17	0 / 100	135 ms	84240 KiB

printer

/*
Author : detective conan
Problem : IOI8_printer
*/
#include <bits/stdc++.h>
#define int long long
#define FFOR(i, s, t) for (int i = s; i <= t; ++i)
#define FBOR(i, s, t) for (int i = s; i >= t; --i)
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod (int)(1e9 + 7)
#define HAVE_TESTCASE false
#define sum(a, b) ((a + b) % mod)
#define mul(a, b) (((a % mod) * (b % mod)) % mod)
#define N (int)(25000)
#define NODE (int)(500100)
#define conan cin.tie(nullptr)->sync_with_stdio(false)

using namespace std;

int n, vis[NODE], depth[NODE], pre[NODE];
string s[N + 10];
unordered_map<int, unordered_map<char, int>> trie; 
vector<char> ans;
unordered_map<int, bool> isEnd;
int nodeCount;

void add(string s){
    int cur = 0;
    for (char c : s) {
        if (trie[cur].find(c) == trie[cur].end()) trie[cur][c] = ++nodeCount;
        cur = trie[cur][c];
    }
    isEnd[cur] = true;
}

void dfs1(int node, int d){
    depth[node] = d;
    cout << node << ' ' << pre[node] << '\n';
    for (auto &x : trie[node]){
        pre[x.second] = node;  
        dfs1(x.second, d + 1);
    }
}

void dfs2(int node){
    vis[node] = 1;
    if(isEnd[node]) ans.emplace_back('P'); 
    int mn = 1e9;  
    pair<int, int> nxt = {1, '1'}; 
    for(auto x:trie[node]){
        if(vis[x.second]) continue;  
        if(mn > depth[x.second]){  
            mn = depth[x.second];
            nxt = {x.second, x.first};  
        }
    }
    if(mn == 1e9 && node == 0) return;
    if(mn == 1e9){
        ans.emplace_back('-');
        dfs2(pre[node]);  
    }
    else { 
        ans.emplace_back(nxt.second);  
        dfs2(nxt.first); 
    }
}

void solve(){
    cin >> n;
    FFOR(i, 1, n) {
        cin >> s[i];
        add(s[i]);  
    }
    dfs1(0, 0);  
    dfs2(0);  
    while(!ans.empty() && ans.back() != 'P') ans.pop_back();
    ANS(ans.size(), '\n');  
    for(auto x:ans) ANS(x, '\n');  
}

int32_t main() {
    conan;
    int t = 1;
    if (HAVE_TESTCASE) cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10