GYM 101673E（暴搜预处理）

佚名 6年前 (2019-04-08) 随笔 874人围观抢沙发百度已收录

1.不会超过500个不同的串……
2.样例没给has到has是怎么样的，实测是true。
3.记忆化别剪错枝就好，嘤嘤嘤……

const int maxn = 505 + 5;
int n, m, tot;
string s, op, t;
bool can[maxn][maxn][2], used[maxn][2];
map<string, int> id;

void GetId(string s) {
    if (!id[s]) id[s] = ++tot;
}

void dfs(int f, int cur, int op) {
    if (used[cur][op])  return;
    used[cur][op] = can[f][cur][op] = 1;

    rep(i, 1, tot) {
        if (can[cur][i][0]) dfs(f, i, op);
        if (can[cur][i][1]) dfs(f, i, 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n) {
        cin >> s >> op >> t;
        GetId(s), GetId(t);
        can[id[s]][id[t]][op[0] != 'i'] = 1;
    }

    rep(i, 1, tot) {
        init(used, 0);
        dfs(i, i, 0);
    }

    rep(i, 1, m) {
        cin >> s >> op >> t;
        cout << "Query " << i << ": ";
        cout << (can[id[s]][id[t]][op[0] != 'i'] ? "true" : "false") << endl;
    }

    return 0;
}