Submission #53478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
53478	2018-06-30T05:44:24 Z	pce913	CSS (COI14_css)	C++17	30 / 100	146 ms	34876 KB

#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<unordered_map>
#include<algorithm>
using namespace std;
char in[5005];
unordered_map<string, int> mp1, mp2;
string its[10005]; //몇번 아이디를 가지고 있는 녀석의 실제 글자.
int GN1, GN2;
vector<int> a[10005];
set<int> cls[10005];
int parent[10005];
vector<int> v[5005];
bool mode[5005];  //1: 부모-자식관계 노드만 찾기 ,0: 그외
int d;
vector<int> ans;
int get_id(string t){
	if (mp1.count(t))return mp1[t];
	return mp1[t] = ++GN1;
}

int get_class(string t){
	if (mp2.count(t))return mp2[t];
	return mp2[t] = ++GN2;
}

void dfs(int node,int depth){
	bool choose = 1;
	for (int i = 0; i < v[depth].size(); i++){
		if (!cls[node].count(v[depth][i])){
			choose = 0;
			break;
		}
	}
	int ndepth = depth;
	if (choose)
		ndepth++;
	if (depth == d - 1 && choose){
		ans.push_back(node);
		if (ans.size() == 4500){
			int aa = 3;
		}
		for (int i = 0; i < a[node].size(); i++){
			int next = a[node][i];
			dfs(next, depth);
		}
	}
	else if (!mode[depth] || (mode[depth] && choose)){
		for (int i = 0; i < a[node].size(); i++){
			int next = a[node][i];
			dfs(next, ndepth);
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt","w",stdout);
	int n;
	scanf("%d ", &n);
	int cur = 0;
	for (int qq = 0; qq < n; qq++){
		fgets(in, 5001, stdin);
		string s = in;
		s.pop_back();
		if (s.size() > 6){
			string t = "";
			int i = 9;
			for (;s[i]!='\''; i++)
				t.push_back(s[i]);
			if (t == "tdiulonlyn"){
				int aa = 3;
			}

			int nid = get_id(t);
			a[cur].push_back(nid);
			parent[nid] = cur;
			its[nid] = t;
			int b = s.find('\'', i + 1);
			for (int i = b+1;; i++){
				if (s[i] == ' ' || s[i] == '\''){
					int nc = get_class(s.substr(b+1, i - b - 1));
					cls[nid].insert(nc);
					b = i;
					if (s[i] == '\'')break;
				}
			}
			cur = nid;
		}
		else cur = parent[cur];
	}
	int m;
	scanf("%d ",&m);
	for (int qq = 0; qq < m; qq++){
		d = 0;
		ans.clear();
		memset(mode, 0, sizeof(mode));
		fgets(in, 5001, stdin);
		string s = in;
		if (s.back()=='\n'){
			s.pop_back();
		}
		s.push_back(' ');
		int j = 0;
		while (j < s.size()){
			v[d].clear();
			int k = s.find(' ', j);
			string t = "";
			for (int i = j + 1; i <= k; i++){
				if (s[i] == '.' || i == k){
					v[d].push_back(get_class(t));
					t = "";
				}
				else t.push_back(s[i]);
			}
			if (s[k + 1] == '>'){
				mode[d + 1] = 1;
				j = k + 3;
			}
			else j = k + 1;  //다음 .으로 설정하기
			d++;
		}
		dfs(0, 0);
		sort(ans.begin(), ans.end());
		printf("%d ", ans.size());
		int i = 0;
		for (; i < (int)ans.size()-1; i++){
			printf("%s ", its[ans[i]].c_str());
		}
		printf("%s\n", its[ans[i]].c_str());
	}
	return 0;
}

Compilation message

css.cpp: In function 'void dfs(int, int)':
css.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[depth].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~
css.cpp:44:8: warning: unused variable 'aa' [-Wunused-variable]
    int aa = 3;
        ^~
css.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[node].size(); i++){
                   ~~^~~~~~~~~~~~~~~~
css.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a[node].size(); i++){
                   ~~^~~~~~~~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:75:9: warning: unused variable 'aa' [-Wunused-variable]
     int aa = 3;
         ^~
css.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < s.size()){
          ~~^~~~~~~~~~
css.cpp:128:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d ", ans.size());
                 ~~~~~~~~~~^
css.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d ", &n);
  ~~~~~^~~~~~~~~~~
css.cpp:66:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(in, 5001, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~
css.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d ",&m);
  ~~~~~^~~~~~~~~~
css.cpp:101:8: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   fgets(in, 5001, stdin);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	5 ms	2680 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3732 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	4528 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	146 ms	19940 KB	Output is correct
2	Correct	9 ms	19940 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	19940 KB	Output is correct
2	Correct	16 ms	19940 KB	Output is correct

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	19940 KB	Output isn't correct

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	6 ms	19940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	6 ms	19940 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	145 ms	34876 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	121 ms	34876 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-