Submission #1300484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300484		wood	Type Printer (IOI08_printer)	C++20	100 / 100	740 ms	58412 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
#define vint vector<int>
#define vpint vector<pint>
#define vll vector<ll>
#define vpll vector<pll>
#define fast_cin()                                                             \
    ios_base::sync_with_stdio(false);                                          \
    cin.tie(NULL);                                                             \
    cout.tie(NULL)
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define MOD %= 1000000007


const int MAX_NODES = 500005; 
int trie2[MAX_NODES][26];
int depth[MAX_NODES];
bool good[MAX_NODES];
string res;
int nodecnt = 1;
void dfs(int u){
    depth[u] = 1;
    for(int i = 0; i<26; i++){
        if(trie2[u][i]!=-1){
            dfs(trie2[u][i]);
            depth[u] = max(depth[u],depth[trie2[u][i]]+1);
        }
    }
}

void dfs2(int u){
    if(good[u]){
        res+="P";
    }
    for(int i = 0; i<26; i++){
        int v = trie2[u][i];
        if(v>-1&&depth[u]>depth[v]+1){
            res+=i+'a';
            dfs2(v);
        }
    }
    for(int i = 0; i<26; i++){
        int v = trie2[u][i];
        if(v>-1&&depth[u]==depth[v]+1){
            res+=i+'a';
            dfs2(v);
        }
    }
    res+="-";
}

void solve() {
    memset(trie2, -1, sizeof(trie2)); 
    memset(good, 0, sizeof(good));
    memset(depth, 0, sizeof(depth));
    nodecnt = 1;
    int n; cin>>n;
    string s[n];
    for(int i = 0; i<n; i++){
        cin>>s[i];
    }
    int N = MAX_NODES;
    for(int i = 0; i<n; i++){
        int node = 0;
        for(int j = 0; j<s[i].size();j++){
            if(trie2[node][s[i][j]-'a'] == -1) node = trie2[node][s[i][j]-'a'] = nodecnt++;
            else node = trie2[node][s[i][j]-'a'];
        }
        good[node] = true;
    }
    dfs(0);
    dfs2(0);
    while(res.back()=='-') res.pop_back();
    cout<<res.size()<<endl;
    for(auto c : res) cout<<c<<endl;
}
int main() {
    fast_cin();
#ifdef MYPC
    freopen("input.in", "r", stdin);
#else
    string filename="";
    if(!filename.empty()) {
        freopen((filename+".in").c_str(), "r", stdin);
        freopen((filename+".out").c_str(), "w", stdout);
    }
#endif
    int t;
    t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen((filename+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen((filename+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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