oj.uz

Submission #734658

# Submission time Handle Problem Language Result Execution time Memory
734658 2023-05-02T18:33:50 Z Hydrolyzed Type Printer (IOI08_printer) C++14
100 / 100
 106 ms 100528 KB 
/*
 * AUTHOR	: Hydrolyzed~
 * SCHOOL	: RYW
 * TASK		: TYPE PRINTER
 * ALGO		: Trie
 * DATE		: 3 May 2023
 * */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#ifndef _DEBUG
// @==== Libary ====@ //

// @================@ //
#endif

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

// @=== Debugger ===@ //
#ifdef _DEBUG
#include "debug.hpp"
#else
#define dbg(...) 0
#endif
// @================@ //

using ll = long long;

struct node_t{
	int cnt = 0;
	bool done;
	node_t *nxt[26];

	node_t(){
		cnt = 0;
		done = false;
		for(int i=0; i<26; ++i){
			nxt[i] = NULL;
		}
	}
};

struct trie_t{
	node_t root;
	void insert(string s){
		node_t *cur = &root;
		for(int i=0; i<(int)s.size(); ++i){
			if(cur->nxt[s[i] - 'a'] == NULL){
				cur->nxt[s[i] - 'a'] = new node_t();
			}
			cur = cur->nxt[s[i] - 'a'];
		}
		cur->cnt++;
	}
	void check(string s){
		node_t *cur = &root;
		for(int i=0; i<(int)s.size(); ++i){
			cur = cur->nxt[s[i] - 'a'];
			cur->done = true;
		}
	}
} t;

string answer_string;

int dfs(node_t *u){
	int res = u->cnt;
	for(int i=0; i<res; ++i){
		answer_string += "P\n";
	}
	for(int i=0; i<26; ++i){
		if(u->nxt[i] != NULL && u->nxt[i]->done == false){
			answer_string += ((char) (i + 'a'));
			answer_string += "\n";
			res += dfs(u->nxt[i]);
			answer_string += "-\n";
			res += 2;
		}
	}
	for(int i=0; i<26; ++i){
		if(u->nxt[i] != NULL && u->nxt[i]->done == true){
			answer_string += ((char) (i + 'a'));
			answer_string += "\n";
			res += dfs(u->nxt[i]);
			res += 1;
		}
	}
	return res;
}

inline void solution(){
	int n;
	string s, l = "";
	cin >> n;
	for(int i=1; i<=n; ++i){
		cin >> s;
		t.insert(s);
		if(s.size() > l.size()){
			l = s;
		}
	}	
	t.check(l);
	cout << dfs(&t.root) << "\n";
	cout << answer_string;
	return ;
}

signed main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);	
	int q = 1;
//	cin >> q;
	while(q--){
		solution();
	}
	return 0;
}
// https://github.com/MasterIceZ/archive/tree/main/cpp-template

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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 212 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 3 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5960 KB Output is correct
2 Correct 15 ms 12716 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14788 KB Output is correct
2 Correct 8 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 36804 KB Output is correct
2 Correct 96 ms 84460 KB Output is correct
3 Correct 48 ms 43600 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 28672 KB Output is correct
2 Correct 106 ms 100528 KB Output is correct
3 Correct 61 ms 49508 KB Output is correct
4 Correct 89 ms 94796 KB Output is correct