Submission #1263201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263201		Megalosaurus	Type Printer (IOI08_printer)	C++20	30 / 100	120 ms	94996 KiB

printer

// Problem: Word Combinations
// Contest: CSES - CSES Problem Set
// URL: https://cses.fi/problemset/task/1731/
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


const int N = 1e6+5, MOD = 1e9+7;;
int trie[N][31], flag[N], dp[N];
int cont = 1;
vector<char>ans;
void insert(string s)
{
	int node = 0;
	for(auto it:s)
	{
		if(trie[node][it-'a'] == 0) trie[node][it-'a'] = cont++;
		node = trie[node][it-'a'];
	}
	flag[node] = true;
}

void dfs(int node)
{
	if(flag[node]) ans.push_back('P');
	for(int i= 0; i < 26; i++)
	{
		if(trie[node][i] != 0)
		{
			ans.push_back(char(i+'a'));
			dfs(trie[node][i]);
			ans.push_back('-');
		}
	}
}

signed main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		string t;
		cin >> t;
		insert(t);
	}
	dfs(0);
	int cnt = 0, xx = -1, mx = 0, idx = 0;
	for(auto it:ans)
	{
		xx++;
		if(it == '-') cnt++;
		else
		{
			cnt = 0;
		}
		if(cnt > mx)  mx = cnt, idx = xx;
	}
    cout << ans.size()-mx << "\n";
    for(int i = idx+1; i < ans.size(); i++) cout << ans[i] << "\n"; 
    bool f= false;
    vector<char>pk;
    for(int i = idx; i >= 0; i--)
    {
    	if(ans[i] != '-') f = true;
    	if(f) pk.push_back(ans[i]);
    }
    for(int i = pk.size()-1; i >= 0; i--)
    {
    	cout << pk[i] << "\n";
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 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