제출 #1255439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255439		mngoc._.	Type Printer (IOI08_printer)	C++20	0 / 100	163 ms	83072 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NUMBEROFNODE = 2e6 + 5;

vector<char> ans;
int res = 0;
int n;
vector<pair<int , int>> adj[NUMBEROFNODE];
int m;
int sz[NUMBEROFNODE];
int mx = NUMBEROFNODE - 1;
string rem;
struct Trie{
    struct NODE{
    	int child[26];
    	int exist , cnt;
	} nodes[NUMBEROFNODE];	
	int cur;
	Trie() : cur(0){
		memset(nodes[0].child , -1 , sizeof(nodes[0].child));
		nodes[0].exist = nodes[0].cnt = 0;
	};
	
	int new_node(){
		cur++;
		memset(nodes[cur].child , -1  , sizeof(nodes[cur].child));
		nodes[cur].cnt = nodes[cur].exist = 0;
		return cur;
	}
	
	void add_string(string s){
		int pos = 0;
		for(auto f : s){
			int c = f - 'a';
			if(nodes[pos].child[c] == -1){
				nodes[pos].child[c] = new_node();
			}
			pos = nodes[pos].child[c];
			nodes[pos].cnt++;
		}
		nodes[pos].exist++;
	}
	
	void dfs(int h , int u , bool emconhoanhko){
		if(nodes[u].exist){
			cout << 'P' << endl;
		}
		for(int i = 0 ; i < 26 ; i++){
			if(nodes[u].child[i] == -1 || (emconhoanhko && i == rem[h] - 'a')) continue;
			cout << char(i + 'a') << endl;
			dfs(h + 1 , nodes[u].child[i] , 0);
		}
		if(emconhoanhko && h < rem.size() && nodes[u].child[h - 'a'] != -1){
			cout << rem[h] << endl;
			dfs(h + 1 , nodes[u].child[rem[h] - 'a'] , 1);
			return; 
		}
		if(!emconhoanhko) cout << "-\n";	
	}
} trie;






void solve(void){
	cin >> n;
	for(int i = 1;  i <= n ; i++){
		string s; cin >> s;
	    trie.add_string(s);	
	    if(s.size() > rem.size()) rem = s;
	}
	cout << trie.cur * 2 + n - rem.size() << endl;
	trie.dfs(0 , 0 , 1);
	
	
	
	
	
	
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10