oj.uz

Submission #855071

# Submission time Handle Problem Language Result Execution time Memory
855071 2023-09-30T04:16:37 Z vjudge1 Type Printer (IOI08_printer) C++14
0 / 100
 1000 ms 3476 KB 
// 等等，这玩意儿好像跟图论有关
// 有点儿像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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1116 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 78 ms 1620 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 3412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1030 ms 3352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 3476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -