oj.uz

Submission #908703

# Submission time Handle Problem Language Result Execution time Memory
908703 2024-01-16T17:16:59 Z Mathias Type Printer (IOI08_printer) C++14
100 / 100
 135 ms 68036 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5380 KB Output is correct
2 Correct 4 ms 5720 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7904 KB Output is correct
2 Correct 16 ms 11744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13472 KB Output is correct
2 Correct 7 ms 6636 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 26200 KB Output is correct
2 Correct 125 ms 58048 KB Output is correct
3 Correct 66 ms 30408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 21960 KB Output is correct
2 Correct 135 ms 68036 KB Output is correct
3 Correct 79 ms 33864 KB Output is correct
4 Correct 129 ms 64444 KB Output is correct