2018-2019 ACM-ICPC, Asia Seoul Regional Contest J - Starwars

問題ページ
ij = human側からスタートして頂点 にいる，not human側からスタートして頂点 にいる という状態が可能か？ という配列を持つ．もし に到達可能で が同じ である辺が存在したら にも到達することができる．

human側の頂点，not human側の頂点からそれぞれまとめてスタートする複数始点のBFSを行うことで，これらの頂点対に到達することができるかの判定を行うことができる．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m, c, h, b;  
    cin >> n >> m >> c >> h >> b;  
    vector<bool> ishuman(n), isbase(n);  
    REP(i, h) {  
        ll x; cin >> x;  
        ishuman[x] = true;  
    }  
    REP(i, b) {  
        ll x; cin >> x;  
        isbase[x] = true;  
    }  
    vector<vector<PII>> g(n);  
    REP(i, m) {  
        ll s, c, t;  
        cin >> s >> c >> t;  
        g[s].push_back({t, c});  
    }  
  
    vector<ll> x, y;  
    REP(i, n) {  
        if(ishuman[i]) x.push_back(i);  
        else y.push_back(i);  
    }  
  
    vector<vector<bool>> visit(n, vector<bool>(n));  
    queue<PII> que;  
    for(auto i: x) for(auto j: y) {  
        visit[i][j] = true;  
        que.push({i, j});  
    }  
    while(que.size()) {  
        PII p = que.front(); que.pop();  
        for(auto to1: g[p.first]) for(auto to2: g[p.second]) {  
            if(visit[to1.first][to2.first] || to1.second != to2.second) continue;  
            visit[to1.first][to2.first] = true;  
            que.push({to1.first, to2.first});  
        }  
    }  
  
    bool ans = false;  
    REP(i, n) REP(j, n) if(visit[i][j] && isbase[i] && isbase[j]) ans = true;  
    if(ans) cout << "YES" << endl;  
    else cout << "NO" << endl;  
  
    return 0;  
}