fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<string>
  6. #include<vector>
  7. #include<map>
  8. #include<algorithm>
  9. #include<stack>
  10. #include<queue>
  11. #include<set>
  12. #include<utility>
  13. #define ll long long
  14. #define max 747474747LL
  15. using namespace std;
  16. ll arr[7000][6];
  17. struct edge{
  18.        int cost ;
  19.        int a,b;
  20.        }list[30000000];
  21.  
  22. bool cmp(edge a,edge b)
  23. {
  24.      return a.cost>b.cost;
  25.  }
  26.  
  27. int find(int *p,int x)
  28. {
  29.     if(p[x]==x)return x;
  30.     return p[x]=find(p,p[x]);
  31. }
  32.  
  33. void join(int *p,int a,int b)
  34. {
  35.      p[find(p,a)]=find(p,b);
  36.  }
  37.  
  38. int sqr(int n)
  39. {
  40.     ll x=(ll)n*n;
  41.     return (int)(x%max);
  42. }
  43.  
  44. int calc(int a,int b,int d)
  45. {
  46.     int i;
  47.     ll ans=0LL;
  48.  
  49.     for(i=0;i<d;i++)
  50.     {
  51.         ans=ans+sqr(arr[a][i]-arr[b][i]);
  52.     }
  53.     return (int)(ans%max);
  54. }
  55.  
  56.  
  57. int kruskal(int n,int d)
  58. {
  59.     int i,j,k,p[7000];
  60.     ll cost;
  61.  
  62.     for(i=0;i<n;i++)
  63.     p[i]=i;
  64.  
  65.  
  66.     for(i=k=0;i<n;i++)
  67.     for(j=i+1;j<n;j++)
  68.     list[k].a=i, list[k].b=j, list[k++].cost=calc(i,j,d);
  69.  
  70.     sort(list,list+k,cmp);
  71.  
  72.     for(cost=1LL,i=0;i<k;i++)
  73.     if(find(p,list[i].a)!=find(p,list[i].b))
  74.     {
  75.     if(list[i].cost<2)break;
  76.     join(p,list[i].a,list[i].b);
  77.     cost=(cost*list[i].cost)%max;
  78.     }
  79.  
  80.     /*for(i=0;i<n;i++)
  81.     find(p,i);*/
  82.  
  83.     return (int)cost;
  84. }
  85.  
  86.  
  87. int main()
  88. {
  89.     int t,n,d,i,j,k;
  90.     int ans,x;
  91.     scanf("%d",&t);
  92.     while(t--)
  93.     {
  94.         scanf("%d %d",&n,&d);
  95.  
  96.         for(i=0;i<n;i++)
  97.         for(j=0;j<d;j++)
  98.         scanf("%d",&arr[i][j]);
  99.  
  100.  
  101.         ans=kruskal(n,d);
  102.         printf("%d\n",ans);
  103.     }
  104. return 0;
  105. }
  106.  
Success #stdin #stdout 0s 354816KB
comments (?)
stdin
copy 
1
3 2
0 0
-1 -1
1 -1
stdout
copy 
8
https://ideone.com/Judb8O
language:
C++ (gcc 8.3)
created:
11 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!