fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. typedef long long int lli;
  5.  
  6. #define maxsize 250000
  7.  
  8. int main(void){
  9.  
  10.     int i,j,n,c,pos,x,y,num,cs,*size,*cnt,*a,**mat,*out,*sz;
  11.     lli *s;
  12.  
  13.     scanf("%d%d",&n,&c);
  14.     size=(int*)malloc(c*sizeof(int));
  15.     s=(lli*)malloc(c*sizeof(lli));
  16.     cnt=(int*)malloc((n+1)*sizeof(int));
  17.     a=(int*)malloc(maxsize*sizeof(int));
  18.     out=(int*)malloc((n+1)*sizeof(int));
  19.     sz=(int*)malloc(n*sizeof(int));
  20.  
  21.     for(i=1;i<=n;i++)cnt[i]=0;
  22.  
  23.     pos=0;
  24.     for(i=0;i<c;i++){
  25.         scanf("%d",&size[i]);
  26. 	s[i]=0;
  27. 	for(j=0;j<size[i];j++){
  28. 	    scanf("%d",&x);
  29. 	    s[i]+=x;
  30. 	    cnt[x]++;
  31. 	    a[pos++]=x;}}
  32.  
  33.     mat=(int**)malloc((n+1)*sizeof(int*));
  34.     for(i=1;i<=n;i++)mat[i]=(int*)malloc(cnt[i]*sizeof(int));
  35.     for(i=1;i<=n;i++)cnt[i]=0;
  36.     pos=0;for(i=0;i<c;i++)for(j=0;j<size[i];j++){x=a[pos];pos++;mat[x][cnt[x]]=i;cnt[x]++;}
  37.  
  38.     for(i=1;i<=n;i++)out[i]=(i==1);
  39.     sz[0]=1;num=1;
  40.  
  41.     for(i=0;i<num;i++){
  42.         x=sz[i];
  43. 	for(j=0;j<cnt[x];j++){
  44. 	    cs=mat[x][j];
  45. 	    size[cs]--;
  46. 	    s[cs]-=x;
  47. 	    y=s[cs];
  48. 	    if(size[cs]==1&&out[y]==0){out[y]=1;sz[num++]=y;}}}
  49.     printf("%d\n",num);
  50.     return 0;
  51. }
  52.  
Success #stdin #stdout 0s 3168KB
comments (?)
stdin
copy 
10 4
2 1 3
2 3 4
6 1 2 3 4 6 7
4 4 3 2 1
stdout
copy 
4
https://ideone.com/BTBvud
language:
C (gcc 8.3)
created:
8 years ago
visibility:
secret

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!