oj.uz

Submission #293586

# Submission time Handle Problem Language Result Execution time Memory
293586 2020-09-08T08:21:40 Z kshitij_sodani Type Printer (IOI08_printer) C++14
100 / 100
 200 ms 80760 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

typedef long long llo;
#define endl '\n'
int n;
int ma=0;
vector<int> ss;
int pre[500001][26];
int co=0;
vector<pair<int,string>> adj[500001];
int endd[500001];
void insert(string s){
	int cur=0;
	vector<int> kk;
	for(int i=0;i<s.size();i++){
		if(pre[cur][s[i]-'a']==0){
			co+=1;
			pre[cur][s[i]-'a']=co;
			string te="";
			te+=s[i];
			adj[cur].pb({co,te});
		}
		
		cur=pre[cur][s[i]-'a'];
		kk.pb(cur);
	}
	endd[cur]=1;
	if(s.size()>ma){
		ma=s.size();
		ss=kk;
	}
}
int vis[5000001];
void dfs(int no,string tt=""){
	if(no!=0){
		cout<<tt<<endl;
	}
	if(endd[no]){
		cout<<"P"<<endl;
	}
	for(auto j:adj[no]){
		if(vis[j.a]==0){
			dfs(j.a,j.b);
		}
	}
	for(auto j:adj[no]){
		if(vis[j.a]==1){
			dfs(j.a,j.b);
		}
	}
	if(vis[no]==0 and no!=0){
		cout<<"-"<<endl;
	}


}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		insert(s);
	}
	cout<<((co+co-ma+n))<<endl;
	for(auto j:ss){
		vis[j]=1;
	}
	dfs(0);



	return 0;
}

Compilation message

printer.cpp: In function 'void insert(std::string)':
printer.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<s.size();i++){
      |              ~^~~~~~~~~
printer.cpp:32:13: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |  if(s.size()>ma){
      |     ~~~~~~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12172 KB Output is correct
2 Correct 10 ms 12704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13216 KB Output is correct
2 Correct 12 ms 13440 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16000 KB Output is correct
2 Correct 33 ms 20600 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22136 KB Output is correct
2 Correct 21 ms 14112 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 37496 KB Output is correct
2 Correct 170 ms 69880 KB Output is correct
3 Correct 110 ms 42232 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 31992 KB Output is correct
2 Correct 200 ms 80760 KB Output is correct
3 Correct 130 ms 46328 KB Output is correct
4 Correct 173 ms 77688 KB Output is correct