oj.uz

Submission #1107569

# Submission time Handle Problem Language Result Execution time Memory
1107569 2024-11-01T14:16:49 Z vjudge1 Type Printer (IOI08_printer) C++17
0 / 100
 60 ms 42648 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

int trie[500002][26], d[500002], mx[500002], id=0, end_[500002];
constexpr int ROOT = 0;
vector<char> ans;

void dfs(int depth = 0, int cur = ROOT) {
	d[cur] = depth;
	mx[cur] = d[cur];
	for (int i = 0; i < 26; i++) {
		if (!trie[cur][i])
			continue;
		dfs(depth + 1, trie[cur][i]);
		mx[cur] = max(mx[cur], mx[trie[cur][i]]);
	}
}   

void dfs_ans(int cur = ROOT) {
	if (end_[cur])
		ans.push_back('P');
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] == mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] != mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	ans.push_back('-');	
}

void add_string(string const & s) {
	int cur = ROOT;
	for (auto & c : s) {
		int x = c - 'a';
		if (trie[cur][x]) {
			cur = trie[cur][x];
		} else {
			cur = trie[cur][x] = ++id;
		}
	}
	end_[cur] = 1;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin >> n;
	string s;
	for (int i = 0; i < n; i++)
		cin >> s, add_string(s);
	dfs(); dfs_ans();
	while(ans.back() != 'P')
		ans.pop_back();
	cout << (int) ans.size() << '\n';
	for (int i = 0; i < (int) ans.size(); i++) 
		cout << ans[i] << ' ';
	cout << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Line "t p t t t y k d u y v x j b z h q u p P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Line "e e j z a t j m n q x c t n P ... y o s s k u g b k i u f f d P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Line "h j x g q k P - - - - - - i u ... l m w f i r l g b d e v j d P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Line "b h v d x r p t h a P - - - - ... m s g e n n p d l u r n m v P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2640 KB Line "a e d P - - b b b l a u q k f ... - - e y n o r w r b i z a i P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4064 KB Line "a P a i s x l h a g q b j w b ... v i w g d u d c y b a h u w P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 10064 KB Line "a P a c a o P - - - i z j p f ... n i c j t u k m w m l d d z P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 20428 KB Line "a P a d m e P - - - e j u i x ... k w z a k q u b h s t c d q P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 42648 KB Line "a P c P a l g m y p z w e h p ... h i h q z w z o m l n c z u P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 35528 KB Line "a P a P c h f a P - - - s p c ... P - - - j t e a r n h d j e P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -