比赛 |
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;
}