Submission #531491

#	Time	Username	Problem	Language	Result	Execution time	Memory
531491		mmonteiro	Type Printer (IOI08_printer)	C++17	100 / 100	117 ms	52224 KiB

printer

#include "bits/stdc++.h"
 
/*
 * Author: Matheus Monteiro
 */
 
using namespace std;
 
#define _ << " , " <<
#define bug(x) cout << #x << "  >>>>>>>  " << x << endl;
 
// #define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vii vector<ii>
#define LSOne(S) ((S) & (-S))
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
const int MAX = 600010; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9;  //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int trie[MAX][26], next_vertex = 1, n;
int h[MAX], sc[MAX];
bool leaf[MAX];

void add(string &s) {
	int r = 0;
	for(char &c : s) {
		if(!trie[r][c - 'a']) trie[r][c - 'a'] = next_vertex++;
		r = trie[r][c - 'a'];
	}
	leaf[r] = true;
}

int go(int node, int i) {
	return trie[node][i];
}

void dfs_sz(int u) {
    h[u] = 1;
    for(int i = 0; i < 26; ++i) {
		int v = go(u, i);
		if(v) {
			dfs_sz(v);
			
			if(sc[u] == -1) sc[u] = v;

			h[u] = max(h[v] + 1, h[u]);
            if(h[sc[u]] < h[v]) sc[u] = v;
		}
	}
}

string ans;

void dfs(int r) {
	if(leaf[r]) ans.push_back('P');
	char c;
	for(int i = 0; i < 26; ++i) {
		int v = go(r, i);
		if(v == sc[r]) {
			c = char(i + 'a');
			continue;
		}
		if(v) {
			ans.push_back(char(i + 'a'));
			dfs(v);
			ans.push_back('-');
		}
	}
	if(sc[r] > 0) {
		ans.push_back(c);
		dfs(sc[r]);
		ans.push_back('-');
	}
}
 
void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        add(s);
    }

	memset(sc, -1, sizeof(sc));

	dfs_sz(0);
	dfs(0);

	while(ans.back() == '-') ans.pop_back();

	cout << SZ(ans) << '\n';
	for(char c : ans)
		cout << c << '\n';

}
 
int32_t main() {
 
	fastio;
	int t = 1;
	//cin >> t;
	for(int caso = 1; caso <= t; ++caso) {
		//cout << "Case #" << caso << ": ";
		solve();
	}
 
	return 0;
}
 
/*
Before submit:
	Check the corners cases
	Check solution restrictions
 
For implementation solutions:
	Check the flow of the variables
 
For intervals problems:
	Think about two pointers
 
For complete search:
	Think about cuts
 
If you get WA:
	Reread your code looking for stupid typos
	Try various manual testcases 
	Recheck the correctness of your algorithm
	Reread the statement
	Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
	Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
	Change the coder (if you're with a team)
	Give up. You may have other tasks to solve.
*/

• 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