比赛 20150424 评测结果 AAAAAAAAAA
题目名称 物质起源 最终得分 100
用户昵称 cstdio 运行时间 0.024 s
代码语言 C++ 内存使用 0.59 MiB
提交时间 2015-04-24 09:09:02
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int SIZEN=410,SIZEC=16510;
map<string,int> namelis;
string chem[SIZEC];
int tot=0;
int get_id(const string &s){
	//cout<<s<<endl;
	if(namelis.count(s)) return namelis[s];
	else{
		tot++;
		chem[tot]=s;
		return namelis[s]=tot;
	}
}
bool valid(char ch){
	if('a'<=ch&&ch<='z') return true;
	if('A'<=ch&&ch<='Z') return true;
	if('0'<=ch&&ch<='9') return true;
	if(ch=='('||ch==')') return true;
	if(ch=='+'||ch=='=') return true;
	return false;
}
void read_line(vector<string> &a,vector<string> &b){//a是反应物,b是生成物
	string now="";
	bool flag=0;
	char ch;
	while(!valid(ch=getchar()));
	now+=ch;
	while(true){
		ch=getchar();
		if(!valid(ch)||ch=='+'||ch=='='){
			get_id(now);//往map里放一下
			if(!flag) a.push_back(now);
			else b.push_back(now);
			if(ch=='+') now="";
			else if(ch=='=') flag=1,now="";
			else break;
		}
		else now+=ch;
	}
}
int N,M;
vector<string> in[SIZEN],out[SIZEN];
bool own[SIZEN][30];
int cnt[SIZEN]={0};
vector<pair<int,int> > rel[SIZEC];
set<string> origin,appear;
void add_comp(const string &s){
	if(appear.count(s)) return;
	appear.insert(s);
	int k=namelis[s];
	for(int i=0;i<rel[k].size();i++){
		int t=rel[k][i].first,j=rel[k][i].second;
		if(own[t][j]) continue;
		own[t][j]=true;
		cnt[t]++;
		if(cnt[t]==in[t].size()){//反应被激活
			for(int r=0;r<out[t].size();r++){
				add_comp(out[t][r]);
			}
		}
	}
}
vector<string> ans;
void work(void){
	//scanf("%d",&M);
	cin>>M;
	string now;
	for(int i=1;i<=M;i++){
		cin>>now;
		origin.insert(now);
		add_comp(now);
	}
	set<string>::iterator key;
	for(key=appear.begin();key!=appear.end();key++){
		if(origin.count(*key)) continue;
		ans.push_back(*key);
	}
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
}
void init(void){
	//scanf("%d",&N);
	cin>>N;
	for(int i=1;i<=N;i++) read_line(in[i],out[i]);
	for(int i=1;i<=N;i++){
		for(int j=0;j<in[i].size();j++){
			rel[get_id(in[i][j])].push_back(make_pair(i,j));
		}
	}
}
int main(){
	freopen("origin.in","r",stdin);
	freopen("origin.out","w",stdout);
	init();
	work();
	return 0;
}