NC213813. 条件
描述
输入描述
第一行四个正整数。
接下来行，每行两个正整数 x,y，描述一条存在的边。
接下来行，每行两个正整数 x,y，描述一条不存在的边。
接下来 q 行，每行两个正整数 x,y，描述一个询问。保证：，
，
，给出的条件不矛盾，不存在自环。
输出描述
输出 q 行，每行两个字符串，均为 Yes 或者 No，第一个表示问题一的答案，第二个表示问题二的答案。
示例1
输入:
4 4 3 7 1 2 2 4 2 3 3 2 4 3 4 2 4 1 1 2 3 1 4 1 2 4 3 4 2 3 1 1
输出:
Yes Yes No Yes No No Yes Yes Yes Yes Yes Yes Yes Yes
C++ 解法, 执行用时: 262ms, 内存消耗: 2192K, 提交时间: 2022-07-08 19:15:53
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+3;
int n,m1,m2,q;
bitset<N>dp1[N],dp2[N];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m1>>m2>>q;
for(int i=1;i<=n;++i)dp2[i].set();
for(int i=1;i<=n;++i)dp1[i][i]=1;
for(int i=1;i<=m1;++i){
int x,y;cin>>x>>y;
dp1[x][y]=1;
}
for(int i=1;i<=m2;++i){
int x,y;cin>>x>>y;
dp2[x][y]=0;
}
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
if(dp1[i][k])dp1[i]|=dp1[k];
if(dp2[i][k])dp2[i]|=dp2[k];
}
}
while(q--){
int x,y;cin>>x>>y;
if(dp1[x][y])cout<<"Yes ";
else cout<<"No ";
if(dp2[x][y])cout<<"Yes\n";
else cout<<"No\n";
}
}