| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一个大水题怎么这么点人A???#include <iostream>
#include <stdio.h>
using namespace std;
int num, cat, mouse;
int catDoors[105][105];
int catDoorsNum[105] = {0};
int mouseDoors[105][105];
int mouseDoorsNum[105] = {0};
bool mouseDoorsMtx[105][105] = {0};
void init(){
for(int i = 1; i <= num; i++) catDoorsNum[i]=0;
for(int i = 1; i <= num; i++) mouseDoorsNum[i] = 0;
for(int i = 1; i <= num; i++)
for(int j = 1; j <= num; j++)
mouseDoorsMtx[i][j] = 0;
}
void dfs(int cm, bool *used, bool isCat){
if(isCat){
used[cm] = 1;
for(int i = 0; i < catDoorsNum[cm]; i++){
if(!used[catDoors[cm][i]]){
dfs(catDoors[cm][i], used, 1);
}
}
}
else{
used[cm] = 1;
for(int i = 0; i < mouseDoorsNum[cm]; i++){
if(!mouseDoorsMtx[cm][mouseDoors[cm][i]]) continue;
if(!used[mouseDoors[cm][i]]){
dfs(mouseDoors[cm][i], used, 0);
}
}
}
}
int main() {
int t;
scanf("%d", &t);
for(int ii = 0; ii < t; ii++){
scanf("%d%d%d", &num, &cat, &mouse);
init();
while(1){
int from, to;
scanf("%d%d", &from, &to);
if(from == -1) break;
catDoors[from][catDoorsNum[from]] = to;
catDoorsNum[from]++;
}
while(1){
int from, to;
scanf("%d%d", &from, &to);
if(from == -1) break;
mouseDoors[from][mouseDoorsNum[from]] = to;
mouseDoorsNum[from]++;
mouseDoorsMtx[from][to] = 1;
}
bool catUsed[105] = {0};
bool mouseUsed[105] = {0};
dfs(cat, catUsed, 1);
dfs(mouse, mouseUsed, 0);
bool xy = 0;
for(int i = 1; i <= num; i++){
if(catUsed[i] && mouseUsed[i]){
xy = 1;
break;
}
}
if(xy) printf("Y ");
else printf("N ");
if(catUsed[mouse]){
printf("N\n");
continue;
}
for(int i = 1; i <= num; i++){
for(int j = 0; j < mouseDoorsNum[i]; j++){
if(catUsed[i] || catUsed[mouseDoors[i][j]]){
mouseDoorsMtx[i][mouseDoors[i][j]] = 0;
}
}
}
bool msUsed[105] = {0};
dfs(mouse, msUsed, 0);
bool ky = 0;
for(int i = 1; i <= num; i++){
if(i == mouse) continue;
if(msUsed[i] && mouseDoorsMtx[i][mouse]){
ky = 1;
break;
}
}
if(ky) printf("Y\n");
else printf("N\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator