fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. #define maxn 222222
  6.  
  7. int n,m,s,k1,k2,i,win[maxn],winner[maxn],f[maxn],t[maxn],p[maxn],ii,was[maxn],c1,c2,c[maxn],k,x,y,ans;
  8.  
  9. void addedge(int x,int y){t[++ii]=y;p[ii]=f[x];f[x]=ii;}
  10.  
  11. int dfs(int k){
  12. 	if(win[k])return (winner[k]=win[k]);
  13. 	if(was[k])return 0;
  14. 	was[k]=1;
  15. 	int q=f[k],w1=0,w2=0,w0=0;
  16. 	while(q){
  17. 		if(winner[t[q]]==-1){
  18. 			winner[t[q]]=dfs(t[q]);
  19. 			if(winner[t[q]]==1)++w1;else
  20. 			if(winner[t[q]]==2)++w2;else ++w0;
  21. 		}
  22. 		q=p[q];
  23. 	}
  24. 	c1=(c[k])/2;c2=c[k]-1-c1;
  25. 	if(w1&&c1>=w2+w0)return (winner[k]=1);
  26. 	if(w2&&c2>=w1+w0)return (winner[k]=2);
  27. 	return (winner[k]=0);
  28. }
  29.  
  30. int main(){
  31. 	freopen("graphgame.in","r",stdin);
  32. 	freopen("graphgame.out","w",stdout);
  33. 	scanf("%d%d%d%d%d",&n,&m,&s,&k1,&k2);
  34. 	for(i=1;i<=k1+k2;i++){
  35. 		scanf("%d",&k);
  36. 		win[k]=1+(i>k1);
  37. 	}
  38. 	for(i=1;i<=m;i++){
  39. 		scanf("%d%d",&x,&y);
  40. 		addedge(x,y);
  41. 		++c[x];
  42. 	}
  43. 	for(i=1;i<=n;i++)winner[i]=-1;
  44. 	ans=dfs(s);
  45. 	if(!ans)puts("Draw");else
  46. 	if(ans==1)puts("Sasha wins");else if(ans==2)puts("Alexandra wins");
  47. 	return 0;
  48. }
Success #stdin #stdout 0.02s 8800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AYV1K
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!