Submission #643770

#	Time	Username	Problem	Language	Result	Execution time	Memory
643770		ymm	Type Printer (IOI08_printer)	C++17	100 / 100	142 ms	99636 KiB

printer

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

struct node {
	node *child[26];
	char mx;
	bool leaf;
} rt;

void add(string s)
{
	node *t = &rt;
	for (char c : s) {
		c -= 'a';
		if (!t->child[c])
			t->child[c] = new node;
		t = t->child[c];
	}
	t->leaf = 1;
}

vector<char> ans;
int dfs1(node *t, int h)
{
	int mx = h;
	Loop (i,0,26) {
		if (t->child[i]) {
			int x = dfs1(t->child[i], h+1);
			if (x > mx) {
				mx = x;
				t->mx = i;
			}
		}
	}
	return mx;
}
void dfs2(node *t, bool ret)
{
	if (t->leaf)
		ans.push_back('P');
	Loop (i,0,26) {
		if ((ret || i != t->mx) && t->child[i]) {
			ans.push_back(i+'a');
			dfs2(t->child[i], 1);
			ans.push_back('-');
		}
	}
	if (!ret && t->child[t->mx]) {
		ans.push_back(t->mx+'a');
		dfs2(t->child[t->mx], 0);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n;
	cin >> n;
	Loop (i,0,n) {
		string s;
		cin >> s;
		add(s);
	}
	dfs1(&rt, 0);
	dfs2(&rt, 0);
	cout << ans.size() << '\n';
	for (char c : ans)
		cout << c << '\n';
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string)':
printer.cpp:20:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   if (!t->child[c])
      |                 ^
printer.cpp:21:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |    t->child[c] = new node;
      |             ^
printer.cpp:22:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |   t = t->child[c];
      |                ^
printer.cpp: In function 'void dfs2(node*, bool)':
printer.cpp:53:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |  if (!ret && t->child[t->mx]) {
      |                       ~~~^~
printer.cpp:55:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |   dfs2(t->child[t->mx], 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