oj.uz

Submission #875465

# Submission time Handle Problem Language Result Execution time Memory
875465 2023-11-19T19:28:02 Z RandomChicken Type Printer (IOI08_printer) C++11
100 / 100
 99 ms 47640 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define f0r(i,n) for(ll i = 0; i<(ll)(n); i++)
#define fir(it,d) for(auto it = d.begin(); it!=d.end(); it++)


struct node{
	char c;
	ll endings;
	vll crs;
	ll depth;
	ll pr;
	bool hasLast;
};

vector<node> trie(1,{'@',0,vll(0),0,0,false});
vector<char> ans;

void addString(string s){
	ll tId = 0;
	f0r(sId,s.size()){
		bool found = false;
		f0r(i,trie[tId].crs.size()){
			if(trie[trie[tId].crs[i]].c==s[sId]){
				tId = trie[tId].crs[i];
				found = true;
				break;
			}
		}
		if(!found){
			trie[tId].crs.push_back(trie.size());
			trie.push_back({s[sId],0,vll(0),trie[tId].depth+1,tId,false});
			tId = trie.size()-1;
		}
	}
	trie[tId].endings++;
}
bool thing(ll a, ll b){
	return(trie[a].hasLast+0<trie[b].hasLast+0);
}
void dfs(ll id){
	if(id) ans.push_back(trie[id].c);
	f0r(i,trie[id].endings) ans.push_back('P');
	sort(trie[id].crs.begin(),trie[id].crs.end(),thing);
	f0r(i,trie[id].crs.size()){
		ll cr = trie[id].crs[i];
		dfs(cr);
	}
	if(id) ans.push_back('-');
}
bool compSize(string a, string b){
	return(a.size()<b.size());
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);


	ll n;
	cin>>n;
	vector<string> inps(n);
	f0r(i,n){
		cin>>inps[i];
	}
	sort(inps.begin(),inps.end(),compSize);
	f0r(i,n){
		addString(inps[i]);
	}
	ll deepest = 0;
	f0r(i,trie.size()){
		if(trie[i].depth>trie[deepest].depth) deepest = i;
	}
	for(ll i = deepest; i!=0; i=trie[i].pr){
		trie[i].hasLast = true;
	}
	dfs(0);
	while(ans.size()&&ans.back()=='-'){
		ans.pop_back();
	}
	cout<<ans.size()<<"\n";
	f0r(i,ans.size()){
		cout<<ans[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1044 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3076 KB Output is correct
2 Correct 14 ms 7372 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7152 KB Output is correct
2 Correct 11 ms 2316 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22976 KB Output is correct
2 Correct 88 ms 43656 KB Output is correct
3 Correct 52 ms 23548 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 13788 KB Output is correct
2 Correct 99 ms 47640 KB Output is correct
3 Correct 56 ms 24828 KB Output is correct
4 Correct 86 ms 45548 KB Output is correct