GRD3-T02: Werewolf

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 3000;

vector<int> adj[N + 10];
int nVertex, nEdge, Q, limHuman, limWerewolf;

int main(){

    scanf("%d %d %d", &nVertex, &nEdge, &Q);
    for(int i = 1; i <= nEdge; ++i){
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int q = 1; q <= Q; ++q){
        int st, ed;
        scanf("%d %d %d %d", &st, &ed, &limHuman, &limWerewolf);
        queue<pii> qu;
        vector<vector<bool>> visited(nVertex + 1, vector<bool>(2, false));
        qu.emplace(st, 0);
        visited[st][0] = true;
        bool complete = false;
        while(!qu.empty()){
            int u = qu.front().first;
            int ww = qu.front().second;
            qu.pop();
            if(u == ed && ww == 1){
                cout << "1\n";
                complete = true;
                break;
            }
            if(!visited[u][1] && u >= limHuman && u <= limWerewolf){
                qu.emplace(u, 1);
                visited[u][1] = true;
            }
            for(int v : adj[u]){
                if(ww == 0 && !visited[v][0] && v >= limHuman){
                    qu.emplace(v, 0);
                    visited[v][0] = true;
                } else if(ww == 1 && !visited[v][1] && v <= limWerewolf){
                    qu.emplace(v, 1);
                    visited[v][1] = true;
                }
            }
        }
        if(!complete){
            cout << "0\n";
        }
    }

    return 0;
}