oj.uz

Submission #1023501

# Submission time Handle Problem Language Result Execution time Memory
1023501 2024-07-14T21:30:49 Z CodeAssignment Type Printer (IOI08_printer) C++17
0 / 100
 122 ms 54340 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);

	set<Node*> vis;
	auto dfs = [&](auto &self, Node* v) -> void {
		vis.insert(v);
		ll letter = v->ch;
		if (letter != -1) cout << char(letter + 'a') << el;
		if (v->isWord) {
			cout << 'P' << el;
		}
		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) cout << '-' << el;
	};
	dfs(dfs, root);
		
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Expected integer, but "n" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Expected integer, but "h" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Expected integer, but "t" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Expected integer, but "w" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2652 KB Expected integer, but "v" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 8796 KB Expected integer, but "r" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 21660 KB Expected integer, but "x" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 54340 KB Expected integer, but "v" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 42696 KB Expected integer, but "p" found
2 Halted 0 ms 0 KB -