oj.uz

Submission #385455

# Submission time Handle Problem Language Result Execution time Memory
385455 2021-04-04T10:53:35 Z negar_a Type Printer (IOI08_printer) C++14
20 / 100
 89 ms 35716 KB 
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 25e3 * 20 + 5;
int mat[maxn][26], h[maxn], mh[maxn];
vector <pair <int, char>> adj[maxn];
vector <char> ans;

int cnt = 1;
void add(string s, int v, int h){
	if(h == s.size()){
		return;
	}
	if(!mat[v][s[h] - 'a']){
		mat[v][s[h] - 'a'] = cnt;
		adj[v].pb({cnt, s[h]});
		cnt ++;
	}
	add(s, mat[v][s[h] - 'a'], h + 1);
}

bool cmp(pair <int, char> a, pair <int, char> b){
	return mh[a.F] < mh[b.F];
}

void dfs(int v){
	sort(adj[v].begin(), adj[v].end(), cmp);
	if(!adj[v].size()){
		ans.pb('P');
	}
	for(auto p : adj[v]){
		int u = p.F;
		ans.pb(p.S);
		dfs(u); 
	}
	ans.pb('-');
}
void dfs1(int v){
	mh[v] = h[v];
	for(auto p : adj[v]){
		int u = p.F;
		h[u] = h[v] + 1;
		dfs1(u); 
		mh[v] = max(mh[v], mh[u]);
	}
}

int main(){
	fast_io;
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++){
		string s;
		cin >> s;
		add(s, 0, 0);
	}
	dfs1(0);
	dfs(0);
	while(ans.back() == '-'){
		ans.pop_back();
	}
	cout << ans.size() << '\n';
	for(char u : ans){
		cout << u << '\n';
	}
	return 0;
}

Compilation message

printer.cpp: In function 'void add(std::string, int, int)':
printer.cpp:21:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  if(h == s.size()){
      |     ~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12140 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Incorrect 9 ms 12140 KB didn't print every word

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12140 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 13164 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 15852 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 21480 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 35716 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 30308 KB didn't print every word
2 Halted 0 ms 0 KB -