oj.uz

Submission #115190

# Submission time Handle Problem Language Result Execution time Memory
115190 2019-06-05T23:29:10 Z CaroLinda Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 56932 KB 
#include <bits/stdc++.h>

#define pii pair<int,int>
#define lp(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define ff first
#define ss second
#define pb push_back

const int MAXN = 25005;
const int ALF= 30;

using namespace std ;

int n ;
int trie[MAXN*20][ALF] , cnt ;
int separa  = 1 ;
vector<char> ans ;
bool marc[MAXN*20] ;

void add( string str )
{
	
	int t = str.size() ;
	
	int cur = 0 ;
	
	lp(i,0,t)
	{
		
		int k = str[i] - 'a' ;
		
		if(trie[cur][k] == 0) trie[cur][k] = ++cnt ;
		
		cur = trie[cur][k] ;
		
	}
	marc[cur] =true;
}

bool comp(string s1, string s2)
{ return s1.size() > s2.size() ; }

void dfs(int x)
{
	
	if(marc[x]) ans.pb('P') ;
	
	int ok=  -1 ;
	
	lp(i,0,27)
	{
		if( trie[x][i] == separa ) { ok = i+'a' ; continue ; }
		if(trie[x][i] == 0) continue ;
		ans.pb( i + 'a' ) ;
		dfs( trie[x][i] ) ;
		ans.pb('-') ;
	}
	
	if(ok!=-1)
	{
		ans.pb(ok) ;
		dfs(separa++) ;
	}
 	
}

int main()
{
	
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
	
	cin>>n ;
	
	string v[MAXN] ;
	
	cin>>v[0] ;
	
	lp(i,1,n) 
	{
		cin>>v[i] ;
		if( v[i].size() >v[0].size() ) swap(v[0] , v[i]) ;
	}
	
	lp(i,0,n) add(v[i]) ;

	dfs(0) ;
	
	cout<<ans.size()  <<endl ;
	
	lp(i,0,ans.size() ) cout<<ans[i]<<endl ;
	
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
printer.cpp:92:5:
  lp(i,0,ans.size() ) cout<<ans[i]<<endl ;
     ~~~~~~~~~~~~~~              
printer.cpp:92:2: note: in expansion of macro 'lp'
  lp(i,0,ans.size() ) cout<<ans[i]<<endl ;
  ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 13 ms 1664 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1920 KB Output is correct
2 Correct 26 ms 2176 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4224 KB Output is correct
2 Correct 150 ms 8056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 9204 KB Output is correct
2 Correct 55 ms 2944 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 21484 KB Output is correct
2 Execution timed out 1030 ms 48356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 16932 KB Output is correct
2 Execution timed out 1079 ms 56932 KB Time limit exceeded
3 Halted 0 ms 0 KB -