oj.uz

Submission #908699

# Submission time Handle Problem Language Result Execution time Memory
908699 2024-01-16T17:09:06 Z Mathias Type Printer (IOI08_printer) C++14
60 / 100
 8 ms 8028 KB 
#include <bits/stdc++.h>
using namespace std;
const int ALF = 30;
const int MAXN = 25e3+7;
int t[MAXN][ALF],depth[MAXN*ALF],md[MAXN*ALF];
bool visited[MAXN*ALF],visited1[MAXN*ALF],ks[MAXN*ALF];
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:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int i=0;i<s.size();i++){
      |               ~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8028 KB Output is correct
2 Runtime error 7 ms 6488 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 6492 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 5 ms 6488 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 5 ms 6492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -