oj.uz

Submission #643770

# Submission time Handle Problem Language Result Execution time Memory
643770 2022-09-23T02:24:07 Z ymm Type Printer (IOI08_printer) C++17
100 / 100
 142 ms 99636 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 4 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5992 KB Output is correct
2 Correct 18 ms 12484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14772 KB Output is correct
2 Correct 7 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 36624 KB Output is correct
2 Correct 118 ms 83668 KB Output is correct
3 Correct 82 ms 43188 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28616 KB Output is correct
2 Correct 142 ms 99636 KB Output is correct
3 Correct 75 ms 48952 KB Output is correct
4 Correct 115 ms 94000 KB Output is correct