oj.uz

Submission #1099825

# Submission time Handle Problem Language Result Execution time Memory
1099825 2024-10-12T05:30:51 Z horezushol Type Printer (IOI08_printer) C++14
10 / 100
 54 ms 36552 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using ll = long long;
using namespace std;

const int N = 25100 * 21;
int nam = 0;
int n;
int trie[N][27];
int dp[N][27];
int dep[N][27];
bool stop[N];

void add(string s) {
	int x = 0;
	for (auto c : s) {
		if (!trie[x][c-'a']) {
			trie[x][c-'a'] = ++nam;
		}
		dep[x][c-'a'] = max(dep[x][c-'a'], SZ(s));
		x = trie[x][c-'a'];
	}
	stop[x] = true;
}

vector<char> res;
int fine = 0;
void dfs(int x) {
	if (stop[x]) {
		res.push_back('P');
		fine ++;
	}
	vector<int> topo(27, 0);
	iota(topo.begin(), topo.end(), 0);
	sort(topo.begin(), topo.end(), [&](int a, int b) {
		return dp[x][a] < dp[x][b];
	});
	for (auto c : topo) {
		if (!trie[x][c]) {
			continue;
		}
		res.push_back(c + 'a');
		dfs(trie[x][c]);
	}
	if (fine != n) {
		res.push_back('-');
	}
}

void verkefni() {
	cin >> n;
	string s[n];
	for (int i = 0; i < n; i ++) {
		cin >> s[i];
		add(s[i]);
	}
	dfs(0);
	cout << SZ(res) << nl;
	for (auto el : res) {
		cout << el << nl;
	}
	// for (int i = 0; i <= nam; i ++) {
	// 	for (int j = 0; j < 27; j ++) {
	// 		if (trie[i][j]) {
	// 			cout << "[" << i << ", " << j << "] --> " << trie[i][j] << nl;
	// 			cout << "[" << i << ", " << j << "] --> " << dep[i][j] << nl;
	// 		}
	// 	}
	// }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tst = 1;
// 	cin >> tst;
	while (tst --) {
		verkefni();
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 14680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 36552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 28796 KB Output isn't correct
2 Halted 0 ms 0 KB -