oj.uz

답안 #226658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226658 2020-04-24T17:05:57 Z tushar_2658 Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 84972 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1000000;
string s[maxn];
int t[maxn][26], ed[maxn], cnt[maxn];
int node = 0;
int par[maxn];

void insert(string s){
	int cur = 0;
	for(auto c : s){
		int idx = c - 'a';
		if(!t[cur][idx]){
			t[cur][idx] = ++node;
		}
		par[t[cur][idx]] = cur;
		cur = t[cur][idx];
	}
	ed[cur] = 1;
}

vector<char> v;

void get(int cur){
	cnt[cur] = 1;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			get(t[cur][i]);
			cnt[cur] = max(cnt[cur], cnt[t[cur][i]] + 1);
		}
	}
}

void dfs(int cur){
	if(ed[cur]){
		ed[cur] = 0;
		v.push_back('P');
	}
	vector<pair<int, int>> vv;
	for(int i = 0; i < 26; ++i){
		if(t[cur][i]){
			vv.push_back(make_pair(cnt[t[cur][i]], i));
		}
	}
	sort(vv.begin(), vv.end());
	for(auto i : vv){
		v.push_back((char)(i.second + 'a'));
		dfs(t[cur][i.second]);
		v.push_back('-');
	}
}

int main(int argc, char const *argv[])
{
//	freopen("in.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> s[i];
		insert(s[i]);
	}
	get(0); 	
	dfs(0);
	while(v.back() == '-')v.pop_back();
	cout << v.size() << endl;
	for(auto i : v){
		cout << i << endl;
	}

	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 31616 KB Output is correct
2 Correct 21 ms 31616 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31488 KB Output is correct
2 Correct 20 ms 31744 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31616 KB Output is correct
2 Correct 22 ms 31744 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 31744 KB Output is correct
2 Correct 20 ms 31744 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 31744 KB Output is correct
2 Correct 36 ms 32128 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 32512 KB Output is correct
2 Correct 55 ms 32768 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 34996 KB Output is correct
2 Correct 256 ms 38252 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 294 ms 39416 KB Output is correct
2 Correct 96 ms 33408 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 51184 KB Output is correct
2 Execution timed out 1099 ms 76520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 577 ms 46856 KB Output is correct
2 Execution timed out 1098 ms 84972 KB Time limit exceeded
3 Halted 0 ms 0 KB -