Submission #1218314

#TimeUsernameProblemLanguageResultExecution timeMemory
1218314sunflowerType Printer (IOI08_printer)C++17
30 / 100
158 ms214000 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define MASK(x) (1LL << (x)) #define BIT(x, i) (((x) >> (i)) & 1) #define SZ(x) ((int) (x).size()) #define ALL(a) (a).begin(), (a).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define debug(x) cout << "[" << #x << " = " << (x) << "]" << endl #define left __left #define right __right #define prev __prev #define next __next #define fi first #define se second template <class X, class Y> bool maximize(X &x, Y y) { if (x < y) return x = y, true; else return false; } template <class X, class Y> bool minimize(X &x, Y y) { if (x > y) return x = y, true; else return false; } const int ALPHABET_SIZE = 26; struct Node { Node* child[ALPHABET_SIZE]; int sz, cnt; Node() { REP(i, ALPHABET_SIZE) child[i] = nullptr; sz = 0; cnt = 0; } }; typedef Node* node; #define MAX_NODE 1'000'200 Node nodes[MAX_NODE + 2]; int trieNode; Node *root; Node* createNode() { // Node *ret = new Node(); // return ret; return &nodes[trieNode++]; } void addString(const string &s) { Node* p = root; for (char c : s) { int x = c - 'a'; if (p->child[x] == nullptr) p->child[x] = createNode(); p = p->child[x]; p->sz++; } p->cnt++; } void dfs(Node *u) { REP(i, ALPHABET_SIZE) { if (u->child[i] == nullptr) continue; dfs(u->child[i]); u->sz += u->child[i]->sz; } } vector <char> opt; void calc(Node *u, int c) { if (c != -1) opt.push_back((char) c + 'a'); int heavy = -1, curSize = 0; REP(i, ALPHABET_SIZE) { if (u->child[i] == nullptr) continue; Node *v = u->child[i]; if (heavy == -1 || curSize < v->sz) { curSize = v->sz; heavy = i; } } if (u->cnt > 0) { REP(i, u->cnt) opt.push_back('P'); } if (heavy != -1) { REP(i, ALPHABET_SIZE) { if (i != heavy && u->child[i] != nullptr) calc(u->child[i], i); } calc(u->child[heavy], heavy); } opt.push_back('-'); } int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); root = createNode(); int n; cin >> n; FOR(i, 1, n) { string s; cin >> s; addString(s); } dfs(root); calc(root, -1); while (!opt.empty() && opt.back() == '-') opt.pop_back(); cout << SZ(opt) << "\n"; for (char c : opt) cout << c << "\n"; return 0; } /* Discipline - Calm */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...