oj.uz

Submission #528085

# Submission time Handle Problem Language Result Execution time Memory
528085 2022-02-19T07:33:05 Z aggrovector Type Printer (IOI08_printer) C++17
20 / 100
 425 ms 19060 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,trie[500005][26],last[500005],idx,i,e[500005];
string a[25005];

void insert(string x) {
	int l=x.length();
	int p=0;
	for (int i=0;i<l;i++) {
		if (trie[p][x[i]-'a']==0) {
			idx++;
			trie[p][x[i]-'a']=idx;
			p=trie[p][x[i]-'a'];
		}
		else {
			p=trie[p][x[i]-'a'];
		}
	}
	e[p]=1;
}

void insert1(string x) {
	int l=x.length();
	int p=0;
	for (int i=0;i<l;i++) {
		if (trie[p][x[i]-'a']==0) {
			idx++;
			trie[p][x[i]-'a']=idx;
			p=trie[p][x[i]-'a'];
		}
		else {
			p=trie[p][x[i]-'a'];
		}
		last[p]=1;
	}
	e[p]=1;
}

bool cmp(string x, string y) {
	int lx=x.length();
	int ly=y.length();
	return lx<ly;
}

void dfs(int x) {
	for (int i=0;i<26;i++) {
		if (trie[x][i]>0 && last[trie[x][i]]==0) {
			cout << char(i+'a') << endl;
			dfs(trie[x][i]);
		}
	}
	for (int i=0;i<26;i++) {
		if (trie[x][i]>0 && last[trie[x][i]]==1) {
			cout << char(i+'a') << endl;
			dfs(trie[x][i]);
		}
	}
	if (e[x]==1) {
		cout << 'P' << endl;
	}
	if (last[x]==0) {
		cout << '-' << endl;
	}
}

int main() {
	cin >> n;
	for (i=1;i<=n;i++) {
		cin >> a[i];
	}
	sort(a+1,a+1+n,cmp);
	for (i=1;i<n;i++) {
		insert(a[i]);
	}
	insert1(a[n]);
	last[0]=1;
	cout << idx*2+n-a[n].length() << endl;
	dfs(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1084 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1084 KB Output is correct
2 Correct 1 ms 1088 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1100 KB Output is correct
2 Incorrect 1 ms 1100 KB printed invalid word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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