Codeforces Beta Round #66 参戦記

今回はいまいちでした。Problem Dを解こうとして奮闘し、問題文を読み違えているのかうまくいかず…の繰り返しでした。特に書く事もない大会です。

問題はこちら


以下解答ソースです。
[ProblemD]

1. #include<stdio.h>
2. #include<stdlib.h>
4. typedef struct{
5.   int from;
6.   int to;
7. }road;
9. road *roads;
11. void defprov(int *a,int num,int count,int r);
13. int main(void){
14.   int *cities;
15.   int i,j,k,n,m,count=1;
16.   int tun;
17.   int *hist;
18.   scanf("%d %d %d",&n,&m,&k);
19.   roads=(road *)calloc(m,sizeof(road));
20.   cities=(int *)calloc(n,sizeof(int));
21.   for(i=0;i<m;i++){
22.     scanf("%d %d",&((roads+i)->from),&((roads+i)->to));
23.     ((roads+i)->from)--;
24.     ((roads+i)->to)--;
25.   }
26.   for(i=0;i<n;i++){
27.     if(*(cities+i)==0){
28.       defprov(cities,i,count,m);
29.       count++;
30.     }
31.   }
32.   count--;
33.   hist=(int *)calloc(count,sizeof(int));
34.   for(i=0;i<n;i++) hist[cities[i]-1]++;
35.   count--;
36.   tun=0;
37.   for(i=0;i<=count;i++){
38.     tun+=(k>hist[i])?hist[i]:k;
39.   }
40.   tun=(tun>n/2)?n/2:tun;
41.   free(hist);
42.   if(count>=tun){
43.     printf("%d\n",count-tun);
44.   }else{
45.     printf("0\n");
46.   }
47.   free(cities);
48.   free(roads);
49.   return 0;
50. }
52. void defprov(int *a,int num,int count,int r){
53.   int i;
54.   a[num]=count;
55.   for(i=0;i<r;i++){
56.     if((roads+i)->from==num){
57.       if(a[(roads+i)->to]==count) continue;
58.       defprov(a,(roads+i)->to,count,r);
59.     }
60.   }
61.   return;
62. }