Submission #855070

#	Time	Username	Problem	Language	Result	Execution time	Memory
855070		vjudge1	Type Printer (IOI08_printer)	C++17	0 / 100	1058 ms	3300 KiB

printer

// 等等，这玩意儿好像跟图论有关
// 有点儿像dfs，回溯思路
// CharTree？？？？？？
// 如何让最长的最后算

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

class Tree{
public:
	char val;
	vector<Tree> children;
	
	Tree();
	Tree(char x){val=x;};
};
class Root{
public:
	vector<Tree> children;
};

int n;
string s, output="";
ll ans=0;
Tree *last, *current;  // 指针
string words[20005];
string mx="";

bool in(vector<Tree> v, char val){
	for (int i=0; i<v.size(); i++){
		if (v[i].val==val) return true;
	}
	return false;
}

Tree* find_child(Tree *tree, char x){  // 没有NOne
	for (int i=0; i<tree->children.size(); i++){
		if (tree->children[i].val == x) return &(tree->children[i]);
	}
}

Tree* find_child(Root *tree, char x){  // Root版本
	for (int i=0; i<tree->children.size(); i++){
		if (tree->children[i].val == x) return &(tree->children[i]);
	}
}

void dfs(Tree *tree, bool islast){  // bool标记是否是最后一个（不用输出-）
	output+=tree->val;
	output+="\n";
	ans++;
	if (tree->children.size()==0){
		output+="p\n";  // 完了
		ans++;
	}
	for (int i=0; i<tree->children.size(); i++){
		dfs(&(tree->children[i]), islast&&i==tree->children.size()-1);
	}
	if (!islast){
		output+="-\n";
		ans++;
	}
}

void dfsrt(Root *root){
	for (int i=0; i<root->children.size(); i++){
		dfs(&(root->children[i]), i==root->children.size()-1);
		//if (!(i==root->children.size()-1))output+="-\n", ans++;
	}
}

bool CMP(string s1, string s2){  // 包含mx元素越多，越靠后
	int i=0, j=0;
	while(i<s1.size() and s1[i] == mx[i]) i++;
	while(j<s2.size() and s2[j] == mx[j]) j++;
	return i<j;
}

int main(){
	cin>>n;
	Root root;
	for (int i=1; i<=n; i++){
		cin>>words[i];
		if (words[i].size() > mx.size()) mx=words[i];
	}
	sort(words+1, words+n+1, CMP);
	for (int i=1; i<=n; i++){
		s=words[i];
		if (!in(root.children, s[0])){  // 加枝
			root.children.push_back(Tree(s[0]));
		}
		current=find_child(&root, s[0]);  // 传回第一个字符子树
		for (int i=1; i<s.size(); i++){
			if (!in(current->children, s[i])) current->children.push_back(Tree(s[i]));  // 加枝
			last=current;
			current=find_child(current, s[i]);
		}
	}
	dfsrt(&root);
	cout << ans << "\n" << output;
	return 0;
}

Compilation message (stderr)

printer.cpp: In function 'bool in(std::vector<Tree>, char)':
printer.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i=0; i<v.size(); i++){
      |                ~^~~~~~~~~
printer.cpp: In function 'Tree* find_child(Tree*, char)':
printer.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i=0; i<tree->children.size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp: In function 'Tree* find_child(Root*, char)':
printer.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i=0; i<tree->children.size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp: In function 'void dfs(Tree*, bool)':
printer.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i=0; i<tree->children.size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp:60:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   dfs(&(tree->children[i]), islast&&i==tree->children.size()-1);
      |                                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp: In function 'void dfsrt(Root*)':
printer.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for (int i=0; i<root->children.size(); i++){
      |                ~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp:70:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   dfs(&(root->children[i]), i==root->children.size()-1);
      |                             ~^~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp: In function 'bool CMP(std::string, std::string)':
printer.cpp:77:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  while(i<s1.size() and s1[i] == mx[i]) i++;
      |        ~^~~~~~~~~~
printer.cpp:78:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  while(j<s2.size() and s2[j] == mx[j]) j++;
      |        ~^~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int i=1; i<s.size(); i++){
      |                 ~^~~~~~~~~
printer.cpp: In function 'Tree* find_child(Tree*, char)':
printer.cpp:43:1: warning: control reaches end of non-void function [-Wreturn-type]
   43 | }
      | ^
printer.cpp: In function 'Tree* find_child(Root*, char)':
printer.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

• 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