Submission #908703

#	Time	Username	Problem	Language	Result	Execution time	Memory
908703		Mathias	Type Printer (IOI08_printer)	C++14	100 / 100	135 ms	68036 KiB

printer

#include <bits/stdc++.h>
using namespace std;
const int ALF = 30;
const int MAXN = 25e3+7;
const int MX = 1e6+7;
int t[MAXN*ALF][ALF],depth[MX],md[MX];
bool visited[MX],visited1[MX],ks[MX];
vector<int> ans;
struct str{
	int fi,sc,th;
};
bool comp(str a,str b){
	return a.fi<b.fi;
}
void DFS(int x){
	visited1[x]=1;
	vector<str> v;
	for(int i=0;i<26;i++) if(visited1[t[x][i]]==0 and t[x][i]>0) v.push_back({md[t[x][i]],t[x][i],i});
	sort(v.begin(),v.end(),comp);
	for(auto p:v){
		ans.push_back(p.th);
		if(ks[p.sc]==1) ans.push_back(-1);
		DFS(p.sc);
	}
	ans.push_back(-2);
}
void DFS1(int x,int f){
	visited[x]=1;
	depth[x]=depth[f]+1;
	md[x]=depth[x];
	for(int i=0;i<26;i++) if(visited[t[x][i]]==0 and t[x][i]>0) DFS1(t[x][i],x);
	for(int i=0;i<26;i++) md[x]=max(md[x], md[t[x][i]]);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,cnt=0,x;
	string s;
	cin>>n;
	while(n--){
		cin>>s; x=0;
		for(int i=0;i<s.size();i++){
			if(t[x][s[i]-97]==0) t[x][s[i]-97]=++cnt;
			x=t[x][s[i]-97];
		}
		ks[x]=1;
	}
	DFS1(0,0); DFS(0);
	while(ans[ans.size()-1]==-2) ans.pop_back();
	cout<<ans.size()<<'\n';
	for(auto i:ans){
		if(i==-2) cout<<"-\n";
		else if(i==-1) cout<<"P\n";
		else cout<<char(i+'a')<<'\n';
	}
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i=0;i<s.size();i++){
      |               ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10