oj.uz

Submission #1023502

# Submission time Handle Problem Language Result Execution time Memory
1023502 2024-07-14T21:32:41 Z CodeAssignment Type Printer (IOI08_printer) C++17
100 / 100
 316 ms 149188 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define el "\n"
#define trav(a, x) for (auto &a : x)
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

struct Node {
	Node *child[26];
	bool isWord;
	ll depth;
	int ch;
	Node() {
		isWord = 0; depth = 0; ch = -1;
		rep(i, 0, 26) child[i] = NULL;
	}
};

set<Node*> nodes;

void add_word(Node* root, string &word) {
	Node *cur = root;
	nodes.insert(root);
	trav(c, word) {
		if (cur->child[c - 'a'] == NULL) {
			cur->child[c - 'a'] = new Node();
			cur->child[c - 'a']->ch = c - 'a';
		}
		cur = cur->child[c - 'a'];
		nodes.insert(cur);
	}
	cur->isWord = 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	ll n;
	cin >> n;
	
	Node* root = new Node();
	vector<string> words;

	rep(i, 0, n) {
		string word; cin >> word;
		words.pb(word);
		add_word(root, word);
	}
	ll node_count = sz(nodes);

	auto setup = [&](auto &self, Node* v, ll d) -> ll {
		ll mx = d;
		rep(i, 0, 26) {
			if (v->child[i] != NULL) {
				mx = max(self(self, (v->child[i]), d + 1), mx);
			}
		}
		v->depth = mx;
		return mx;
	};
	setup(setup, root, 0);

	vector<char> ans;
	set<Node*> vis;
	auto dfs = [&](auto &self, Node* v) -> void {
		vis.insert(v);
		ll letter = v->ch;
		if (letter != -1) ans.pb(char(letter + 'a'));
		if (v->isWord) {
			ans.pb('P');
		}
		vector<pair<ll, Node*>> nxt;
		rep(i, 0, 26) {
			if (v->child[i] != NULL) {
				nxt.pb(make_pair(v->child[i]->depth, (v->child[i])));
			}
		}
		//sort(all(nxt), greater<pair<ll, Node*>>());
		sort(all(nxt));
		trav(c, nxt) {
			self(self, c.second);		
		}
		if (sz(vis) < node_count) ans.pb('-');
	};
	dfs(dfs, root);

	cout << sz(ans) << el;
	trav(c, ans) cout << c << el;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 5 ms 3164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8848 KB Output is correct
2 Correct 32 ms 18648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 21968 KB Output is correct
2 Correct 15 ms 5240 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 54724 KB Output is correct
2 Correct 255 ms 125252 KB Output is correct
3 Correct 130 ms 64964 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 42948 KB Output is correct
2 Correct 316 ms 149188 KB Output is correct
3 Correct 155 ms 73928 KB Output is correct
4 Correct 253 ms 140740 KB Output is correct