Submission #386815

#	Time	Username	Problem	Language	Result	Execution time	Memory
386815		minoum	Type Printer (IOI08_printer)	C++17	100 / 100	217 ms	161576 KiB

printer

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e6+10, A = 30;
int t, c[MAXN][A], par[MAXN], h[MAXN], mx = 0, mxid = -1, n = 1;
vector <pair<int,int>> adj[MAXN];
bool mark[MAXN], isword[MAXN];
string ans = "";

inline void add(string s){
	int pt = 0, v = 0;
	while(pt < (int)s.size()){
		int ch = (s[pt]-'a');
		if(c[v][ch] == -1){
			par[n] = v; c[v][ch] = n; h[n] = h[v]+1;
			adj[v].push_back({n, ch}); n++;
		}
		v = c[v][ch];
		if(h[v] > mx) mx = h[v], mxid = v;
		pt++;
		if(pt == (int)s.size()) isword[v] = true;
	}
	return;
}

void dfs(int v, int parv){
	if(isword[v]) ans += 'P';
	for(auto i: adj[v]){
		int u = i.first, ch = i.second;
		if(mark[u]) continue;
		ans += (char)('a'+ch);
		dfs(u, v);
	}
	for(auto i: adj[v]){
		int u = i.first, ch = i.second;
		if(!mark[u]) continue;
		ans += (char)('a'+ch);
		dfs(u, v);
	}
	if(!mark[v]) ans += '-';
	return;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	for(int i = 0; i < MAXN; i++) 
		for(int j = 0; j < A; j++) c[i][j] = -1;
	cin >> t;
	par[0] = -1;
	for(int i = 0; i < t; i++){
		string s;
		cin >> s; add(s);
	}
	int v = mxid;
	while(v != -1){
		mark[v] = true; v = par[v];
	}
	dfs(0,-1);
	cout << (int)ans.size() << '\n';
	for(int i = 0; i < (int)ans.size(); i++) cout << ans[i] << '\n';
	return 0; 
}

• 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