[ICPC 2017 ECNA E]Is-A? Has-A? Who Knowz-A?

Link

Solution

一道大水题,提醒自己用最暴力的方法做最对的事。

Code

const int XN=1000;

std::vector<int> is[XN],has[XN];

int main() {
//  freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    std::map<std::string,int> id;
    int n,m;std::cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;++i) {
        std::string c1,op,c2;
        std::cin>>c1>>op>>c2;
        for(auto & s: { c1,c2 })
            if(!id.count(s))
                id[s]=++cnt;
        int x=id[c1],y=id[c2];
        (op[0]=='i'?is[x]:has[x]).push_back(y);
    }

    for(int ks=1;ks<=m;++ks) {
        std::cout<<"Query "<<ks<<": ";
        std::string c1,op,c2;
        std::cin>>c1>>op>>c2;
        int x=id[c1],y=id[c2];
        bool tak=0;
        if(op[0]=='i') {
            std::queue<int> Q;
            std::set<int> S;
            Q.push(x);
            S.insert(x);
            while(!Q.empty()) {
                int pos=Q.front();Q.pop();
                for(auto u : is[pos]) {
                    if(u==y) {
                        tak=1;
                        goto out;
                    }
                    if(!S.count(u)) {
                        S.insert(u);
                        Q.push(u);
                    }
                }
            }
            tak=S.count(y);
        } else {
            std::queue<std::pair<int,bool>> Q;
            std::set<std::pair<int,bool>> S;
            Q.push({x,0});
            S.insert({x,0});
            while(!Q.empty()) {
                auto pos=Q.front();Q.pop();
                for(auto u : has[pos.first]) {
                    if(!S.count(std::pair<int,bool>(u,1))) {
                        Q.push({u,1});
                        S.insert({u,1});
                    }
                }
                for(auto u : is[pos.first])
                    if(!S.count(std::pair<int,bool>(u,pos.second))) {
                        Q.push({u,pos.second});
                        S.insert({u,pos.second});
                    }
            }
            tak=S.count({y,1});
        }
out:    std::cout<<(tak?"true":"false")<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注