oj.uz

Submission #1099696

# Submission time Handle Problem Language Result Execution time Memory
1099696 2024-10-12T03:36:20 Z horezushol Type Printer (IOI08_printer) C++14
10 / 100
 13 ms 15452 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;
int nam = 0;
int trie[N][27];
int dp[N][27];	
bool visited[N][27];


void add(int x, string s, int pos) {
	if (pos >= SZ(s)) return ;
	char c = s[pos];
	if (trie[x][c-'a'] == 0) {
		trie[x][c-'a'] = ++nam;
	}
	add(trie[x][c-'a'], s, pos + 1);
	// cout << x << " " << trie[x][c-'a'] << nl;
	if (pos + 1 == SZ(s)) {
		dp[x][c-'a'] = 1;
	} else {
		dp[x][c-'a'] += dp[trie[x][c-'a']][s[pos+1]-'a'] + !visited[x][c-'a'];
		visited[x][c-'a'] = true;		
	}
}

vector<char> res;
vector<pair<int, pair<int, int>>> mn[N];
void PP(int x) {
	if (!x) return ;
	res.push_back('P');
	for (int i = 0; i < x; i ++) {
		res.push_back('-');
	}
}


void dfs(int x) {
	// cout << x << nl;
	int fine = 0;
	for (auto el : mn[x]) {
		PP(fine);
		res.push_back(el.S.F + 'a');
		if (SZ(mn[el.S.S]) > 0) {
			dfs(el.S.S);			
		}
		fine = el.F;
	}
}

void verkefni() {
	int n;
	cin >> n;
	string s[n];
	for (int i = 0; i < n; i ++) {
		cin >> s[i];
		add(0, s[i], 0);
	}
	for (int i = 0; i < N; i ++) {
		for (int j = 0; j < 27; j ++) {
			visited[i][j] = false;
		}
	}
	for (int i = 0; i <= nam; i ++) {
		for (int j = 0; j < 27; j ++) {
			if (dp[i][j]) {
				mn[i].push_back({dp[i][j], {j, trie[i][j]}});
			}
		}
	}
	for (int i = 0; i <= nam; i ++) {
		sort(mn[i].begin(), mn[i].end());
	}
	dfs(0);
	res.push_back('P');
	cout << SZ(res) << nl;
	for (int i = 0; i < SZ(res); i ++) {
		cout << res[i];
		if (i == SZ(res)-1) {
		} else {
			cout << nl;
		}
	}
	// for (int i = 0; i <= nam; i ++) {
	// 	for (auto el : mn[i]) {
	// 		cout << "(" << el.F << " " << el.S.F << " " << el.S.S << ") ";
	// 	}
	// 	cout << 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] << " | " << dp[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 1 ms 2652 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 0 ms 2652 KB too many deletions
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2648 KB too many deletions
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2652 KB too many deletions
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3676 KB too many deletions
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8152 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 14428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 15028 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 15452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -