Submission #1099696

#TimeUsernameProblemLanguageResultExecution timeMemory
1099696horezusholType Printer (IOI08_printer)C++14
10 / 100
13 ms15452 KiB
#include<bits/stdc++.h> #define F first #define S second #define SZ(x) int((x).size()) const char nl = '\n'; using ll = long long; using namespace std; const int N = 25100; int nam = 0; int trie[N][27]; int dp[N][27]; bool visited[N][27]; void add(int x, string s, int pos) { if (pos >= SZ(s)) return ; char c = s[pos]; if (trie[x][c-'a'] == 0) { trie[x][c-'a'] = ++nam; } add(trie[x][c-'a'], s, pos + 1); // cout << x << " " << trie[x][c-'a'] << nl; if (pos + 1 == SZ(s)) { dp[x][c-'a'] = 1; } else { dp[x][c-'a'] += dp[trie[x][c-'a']][s[pos+1]-'a'] + !visited[x][c-'a']; visited[x][c-'a'] = true; } } vector<char> res; vector<pair<int, pair<int, int>>> mn[N]; void PP(int x) { if (!x) return ; res.push_back('P'); for (int i = 0; i < x; i ++) { res.push_back('-'); } } void dfs(int x) { // cout << x << nl; int fine = 0; for (auto el : mn[x]) { PP(fine); res.push_back(el.S.F + 'a'); if (SZ(mn[el.S.S]) > 0) { dfs(el.S.S); } fine = el.F; } } void verkefni() { int n; cin >> n; string s[n]; for (int i = 0; i < n; i ++) { cin >> s[i]; add(0, s[i], 0); } for (int i = 0; i < N; i ++) { for (int j = 0; j < 27; j ++) { visited[i][j] = false; } } for (int i = 0; i <= nam; i ++) { for (int j = 0; j < 27; j ++) { if (dp[i][j]) { mn[i].push_back({dp[i][j], {j, trie[i][j]}}); } } } for (int i = 0; i <= nam; i ++) { sort(mn[i].begin(), mn[i].end()); } dfs(0); res.push_back('P'); cout << SZ(res) << nl; for (int i = 0; i < SZ(res); i ++) { cout << res[i]; if (i == SZ(res)-1) { } else { cout << nl; } } // for (int i = 0; i <= nam; i ++) { // for (auto el : mn[i]) { // cout << "(" << el.F << " " << el.S.F << " " << el.S.S << ") "; // } // cout << nl; // } // for (int i = 0; i < nam; i ++) { // for (int j = 0; j < 27; j ++) { // if (trie[i][j]) { // cout << "[" << i << ", " << j << "] --> " << trie[i][j] << " | " << dp[i][j] << nl; // } // } // } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tst = 1; // cin >> tst; while (tst --) { verkefni(); } }
#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...