记录编号 |
78145 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
街道赛跑 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.005 s |
提交时间 |
2013-11-03 14:57:15 |
内存使用 |
0.32 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZEN=101;
vector<int> c[SIZEN];
vector<int> onlyway,cut;
bool nowable[SIZEN]={0};
int n;
void DFS(bool flag[SIZEN],int x){
if(!nowable[x]) return;
if(flag[x]) return;
flag[x]=true;
int i;
for(i=0;i<c[x].size();i++) DFS(flag,c[x][i]);
}
void work(void){
int i,j;
bool canreach_start[SIZEN];
bool canreach_middle[SIZEN];
for(i=1;i<n;i++){
memset(nowable,1,sizeof(nowable));
memset(canreach_start,0,sizeof(canreach_start));
nowable[i]=false;
DFS(canreach_start,0);
if(!canreach_start[n]){
onlyway.push_back(i);
memset(canreach_middle,0,sizeof(canreach_middle));
nowable[i]=true;
DFS(canreach_middle,i);
for(j=0;j<=n;j++){
if(j==i) continue;
if(!(canreach_middle[j]^canreach_start[j])) goto END;
}
cut.push_back(i);
}
END:;
}
printf("%d ",onlyway.size());
for(i=0;i<onlyway.size();i++) printf("%d ",onlyway[i]);
printf("\n");
printf("%d ",cut.size());
for(i=0;i<cut.size();i++) printf("%d ",cut[i]);
printf("\n");
}
void read(void){
n=0;
int i=0,x;
while(true){
do{
scanf("%d",&x);
if(x==-1) return;
c[i].push_back(x);
}while(x!=-2);
n=i++;
}
}
int main(){
freopen("race3.in","r",stdin);
freopen("race3.out","w",stdout);
read();
work();
return 0;
}