oj.uz

Submission #915571

# Submission time Handle Problem Language Result Execution time Memory
915571 2024-01-24T07:52:06 Z josanneo22 Type Printer (IOI08_printer) C++17
100 / 100
 95 ms 84820 KB 
#include<bits/stdc++.h>
#include <random>
using namespace std;
namespace NEO{ 
	std::mt19937 cincai(std::chrono::steady_clock::now().time_since_epoch().count());
	using i64 = long long;

	#define pb push_back
	#define mp make_pair
	#define cs constexpr

	#define L(i,j,k) for(int i=(j);i<=(k);++i)
	#define R(i,j,k) for(int i=(j);i>=(k);--i)
	#define all(x) x.begin(),x.end()
	#define me(x,a) memset(x,a,sizeof(x))

	//~ #ifndef ONLINE_JUDGE
	//~ #include "debug.h"
	//~ #else
	//~ #define dbg(...) 43
	//~ #endif
}using namespace NEO;

struct node{
	int nxt[26];
	bool is_longest, finish_word;
	node(){ 
		me(nxt, 0); 
		is_longest = false; 
		finish_word = false;
	}
};
cs int _N = 25000 * 30;
int tot = 0;
node trie[_N];

void build(string S){
	int M = S.size(), P = 0;
	for(int i = 0; i < M; i++){
		int nw = S[i] - 'a';
		if(trie[P].nxt[nw] == 0){
			trie[P].nxt[nw] = ++tot;
			trie[tot] = node();
		}
		P = trie[P].nxt[nw];
	}
	trie[P].finish_word = true;
}
void paint(string S){
	int P = 0;
	for(int i = 0; i < (int)S.size(); i++){
		int nw = S[i] - 'a';
		P = trie[P].nxt[nw];
		trie[P].is_longest = true;
	}
}
string ans = "";
void dfs(int P){
	int longest = -1;
	if(trie[P].finish_word) ans += 'P';
	for(int i = 0; i < 26; i++){
		int next_node = trie[P].nxt[i];
		if(trie[next_node].is_longest) longest = i;
		else if(next_node != 0) {
			ans += (i + 'a');
			dfs(next_node);
		}
	}
	if(longest != -1){
		ans += (longest + 'a');
		dfs(trie[P].nxt[longest]);
	}
	else if(longest == -1 && trie[P].is_longest) return;
	else ans += '-';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	int N; cin >> N;
	vector<string> s(N + 1);
	L(i, 1, N) cin >> s[i];
	string longest = "";
	L(i, 1, N) {
		build(s[i]);
		if(longest.size() < s[i].size()) 	
			longest = s[i];
	}
	paint(longest);
	dfs(0);
	cout << ans.size() << '\n';
	for(auto & c : ans) cout << c << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 79704 KB Output is correct
2 Correct 22 ms 79708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 79444 KB Output is correct
2 Correct 22 ms 79696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 79708 KB Output is correct
2 Correct 21 ms 79516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 79704 KB Output is correct
2 Correct 21 ms 79588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 79700 KB Output is correct
2 Correct 21 ms 79708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 79568 KB Output is correct
2 Correct 22 ms 79708 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 79960 KB Output is correct
2 Correct 30 ms 80472 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 80612 KB Output is correct
2 Correct 25 ms 80468 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 81644 KB Output is correct
2 Correct 89 ms 84076 KB Output is correct
3 Correct 54 ms 83036 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 81648 KB Output is correct
2 Correct 95 ms 84748 KB Output is correct
3 Correct 60 ms 83568 KB Output is correct
4 Correct 81 ms 84820 KB Output is correct