oj.uz

Submission #293585

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

typedef long long llo;

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 9 ms 12032 KB Output is correct
2 Correct 9 ms 12100 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct
2 Correct 9 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 12160 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 13184 KB Output is correct
2 Correct 61 ms 13440 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 22136 KB Output is correct
2 Correct 99 ms 14208 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 37368 KB Output is correct
2 Execution timed out 1095 ms 69752 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 31932 KB Output is correct
2 Execution timed out 1101 ms 80504 KB Time limit exceeded
3 Halted 0 ms 0 KB -