제출 #1313779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313779		algoproclub	Type Printer (IOI08_printer)	C++20	10 / 100	28 ms	11116 KiB

printer

// UUID: a8dbf094-2660-4ade-b544-8339c1ddc896
#include <bits/stdc++.h>
using namespace std;

vector<char> nodes(1, 0);
vector<vector<int>> nbrs(1, vector<int>(0));
vector<bool> vis;
string strans;
int dfs(int Index){
	if(vis[Index]) return 0;
	vis[Index]=true;
	//printf("[%d: %d]", Index, nbrs[Index].size());
	int ans=0;
	for(int x : nbrs[Index]){
		if(!vis[x]){
			strans.push_back(nodes[x]);
			//printf("%c\n", nodes[x]);
			ans+=2+dfs(x);
			strans.push_back('-');
			//printf("-\n");
		}
	}
	if(ans==0){
		strans.push_back('P');
	}
	return ans;
}

int main() {
	int n; cin >> n;
	int maxLen=0;
	vector<pair<int, string>> input(n); for(auto& x : input){
		cin >> x.second;
		x.first=x.second.size();
	}
	sort(input.begin(), input.end());
	for(int i=0;i<n;i++){
		const string& s=input[i].second;
		maxLen=max(maxLen, (int)s.size());
		int curr=0;
		for(char x : s){
			bool found=false;
			for(int y : nbrs[curr]){
				if(x==nodes[y]){
					found=true;
					curr=y;
					break;
				}
			}
			if(!found){
				nbrs[curr].push_back(nbrs.size());
				curr=nbrs.size();
				nbrs.push_back(vector<int>(0));
				nodes.push_back(x);
			}
		}
	}
	vis.resize(nodes.size(), false);
	cout << dfs(0)+n-maxLen << '\n';
	while(strans.back()=='-') strans.pop_back();
	for(char x : strans) cout << x << '\n';
}

• Subtask 1: 10 / 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