fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void*wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  13.   walloc1d(arr, x2-x1, mem);
  14.   (*arr) -= x1;
  15. }
  16. template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
  17.   int i;
  18.   pair<T1, T2>*arr;
  19.   walloc1d(&arr, N, &mem);
  20.   for(i=(0);i<(N);i++){
  21.     arr[i].first = a[i];
  22.     arr[i].second = b[i];
  23.   }
  24.   sort(arr, arr+N);
  25.   for(i=(0);i<(N);i++){
  26.     a[i] = arr[i].first;
  27.     b[i] = arr[i].second;
  28.   }
  29. }
  30. template<class T1, class T2, class T3> void sortA_L(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  31.   int i;
  32.   pair<T1, pair<T2, T3> >*arr;
  33.   walloc1d(&arr, N, &mem);
  34.   for(i=(0);i<(N);i++){
  35.     arr[i].first = a[i];
  36.     arr[i].second.first = b[i];
  37.     arr[i].second.second = c[i];
  38.   }
  39.   sort(arr, arr+N);
  40.   for(i=(0);i<(N);i++){
  41.     a[i] = arr[i].first;
  42.     b[i] = arr[i].second.first;
  43.     c[i] = arr[i].second.second;
  44.   }
  45. }
  46. inline int my_getchar_unlocked(){
  47.   static char buf[1048576];
  48.   static int s = 1048576;
  49.   static int e = 1048576;
  50.   if(s == e && e == 1048576){
  51.     e = fread_unlocked(buf, 1, 1048576, stdin);
  52.     s = 0;
  53.   }
  54.   if(s == e){
  55.     return EOF;
  56.   }
  57.   return buf[s++];
  58. }
  59. inline void rd(int &x){
  60.   int k;
  61.   int m=0;
  62.   x=0;
  63.   for(;;){
  64.     k = my_getchar_unlocked();
  65.     if(k=='-'){
  66.       m=1;
  67.       break;
  68.     }
  69.     if('0'<=k&&k<='9'){
  70.       x=k-'0';
  71.       break;
  72.     }
  73.   }
  74.   for(;;){
  75.     k = my_getchar_unlocked();
  76.     if(k<'0'||k>'9'){
  77.       break;
  78.     }
  79.     x=x*10+k-'0';
  80.   }
  81.   if(m){
  82.     x=-x;
  83.   }
  84. }
  85. struct MY_WRITER{
  86.   char buf[1048576];
  87.   int s;
  88.   int e;
  89.   MY_WRITER(){
  90.     s = 0;
  91.     e = 1048576;
  92.   }
  93.   ~MY_WRITER(){
  94.     if(s){
  95.       fwrite_unlocked(buf, 1, s, stdout);
  96.     }
  97.   }
  98. }
  99. ;
  100. MY_WRITER MY_WRITER_VAR;
  101. void my_putchar_unlocked(int a){
  102.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  103.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  104.     MY_WRITER_VAR.s = 0;
  105.   }
  106.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  107. }
  108. inline void wt_L(char a){
  109.   my_putchar_unlocked(a);
  110. }
  111. inline void wt_L(int x){
  112.   int s=0;
  113.   int m=0;
  114.   char f[10];
  115.   if(x<0){
  116.     m=1;
  117.     x=-x;
  118.   }
  119.   while(x){
  120.     f[s++]=x%10;
  121.     x/=10;
  122.   }
  123.   if(!s){
  124.     f[s++]=0;
  125.   }
  126.   if(m){
  127.     my_putchar_unlocked('-');
  128.   }
  129.   while(s--){
  130.     my_putchar_unlocked(f[s]+'0');
  131.   }
  132. }
  133. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  134.   int i;
  135.   sz++;
  136.   for(i=sz-1;i>k;i--){
  137.     a[i] = a[i-1];
  138.   }
  139.   a[k] = aval;
  140. }
  141. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  142.   int i;
  143.   sz++;
  144.   for(i=sz-1;i>k;i--){
  145.     a[i] = a[i-1];
  146.   }
  147.   for(i=sz-1;i>k;i--){
  148.     b[i] = b[i-1];
  149.   }
  150.   a[k] = aval;
  151.   b[k] = bval;
  152. }
  153. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  154.   int i;
  155.   sz++;
  156.   for(i=sz-1;i>k;i--){
  157.     a[i] = a[i-1];
  158.   }
  159.   for(i=sz-1;i>k;i--){
  160.     b[i] = b[i-1];
  161.   }
  162.   for(i=sz-1;i>k;i--){
  163.     c[i] = c[i-1];
  164.   }
  165.   a[k] = aval;
  166.   b[k] = bval;
  167.   c[k] = cval;
  168. }
  169. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  170.   int i;
  171.   sz++;
  172.   for(i=sz-1;i>k;i--){
  173.     a[i] = a[i-1];
  174.   }
  175.   for(i=sz-1;i>k;i--){
  176.     b[i] = b[i-1];
  177.   }
  178.   for(i=sz-1;i>k;i--){
  179.     c[i] = c[i-1];
  180.   }
  181.   for(i=sz-1;i>k;i--){
  182.     d[i] = d[i-1];
  183.   }
  184.   a[k] = aval;
  185.   b[k] = bval;
  186.   c[k] = cval;
  187.   d[k] = dval;
  188. }
  189. struct unionFind{
  190.   int*d;
  191.   int N;
  192.   int M;
  193.   inline void malloc(const int n){
  194.     d = (int*)std::malloc(n*sizeof(int));
  195.     M = n;
  196.   }
  197.   inline void malloc(const int n, const int fg){
  198.     d = (int*)std::malloc(n*sizeof(int));
  199.     M = n;
  200.     if(fg){
  201.       init(n);
  202.     }
  203.   }
  204.   inline void free(void){
  205.     std::free(d);
  206.   }
  207.   inline void walloc(const int n, void **mem=&wmem){
  208.     walloc1d(&d, n, mem);
  209.     M = n;
  210.   }
  211.   inline void walloc(const int n, const int fg, void **mem=&wmem){
  212.     walloc1d(&d, n, mem);
  213.     M = n;
  214.     if(fg){
  215.       init(n);
  216.     }
  217.   }
  218.   inline void init(const int n){
  219.     int i;
  220.     N = n;
  221.     for(i=(0);i<(n);i++){
  222.       d[i] = -1;
  223.     }
  224.   }
  225.   inline void init(void){
  226.     init(M);
  227.   }
  228.   inline int get(int a){
  229.     int t = a;
  230.     int k;
  231.     while(d[t]>=0){
  232.       t=d[t];
  233.     }
  234.     while(d[a]>=0){
  235.       k=d[a];
  236.       d[a]=t;
  237.       a=k;
  238.     }
  239.     return a;
  240.   }
  241.   inline int connect(int a, int b){
  242.     if(d[a]>=0){
  243.       a=get(a);
  244.     }
  245.     if(d[b]>=0){
  246.       b=get(b);
  247.     }
  248.     if(a==b){
  249.       return 0;
  250.     }
  251.     if(d[a] < d[b]){
  252.       d[a] += d[b];
  253.       d[b] = a;
  254.     }
  255.     else{
  256.       d[b] += d[a];
  257.       d[a] = b;
  258.     }
  259.     return 1;
  260.   }
  261.   inline int operator()(int a){
  262.     return get(a);
  263.   }
  264.   inline int operator()(int a, int b){
  265.     return connect(a,b);
  266.   }
  267.   inline int& operator[](const int a){
  268.     return d[a];
  269.   }
  270.   inline int size(int a){
  271.     a = get(a);
  272.     return -d[a];
  273.   }
  274.   inline int sizeList(int res[]){
  275.     int i;
  276.     int sz=0;
  277.     for(i=(0);i<(N);i++){
  278.       if(d[i]<0){
  279.         res[sz++] = -d[i];
  280.       }
  281.     }
  282.     return sz;
  283.   }
  284. }
  285. ;
  286. int N;
  287. int A[500][500];
  288. int m;
  289. int x[200000];
  290. int y[200000];
  291. int z[200000];
  292. int main(){
  293.   int i;
  294.   wmem = memarr;
  295.   int res = 0;
  296.   unionFind uf;
  297.   rd(N);
  298.   {
  299.     int Lj4PdHRW;
  300.     int KL2GvlyY;
  301.     for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
  302.       for(KL2GvlyY=(0);KL2GvlyY<(N);KL2GvlyY++){
  303.         rd(A[Lj4PdHRW][KL2GvlyY]);
  304.       }
  305.     }
  306.   }
  307.   for(i=(0);i<(N);i++){
  308.     int j;
  309.     for(j=(i+1);j<(N);j++){
  310.       arrInsert(m, m, x, i, y, j, z, A[i][j]);
  311.     }
  312.   }
  313.   sortA_L(m, z, x, y);
  314.   uf.malloc(2*N,1);
  315.   for(i=(0);i<(m);i++){
  316.     res = z[i];
  317.     uf(x[i], y[i]+N);
  318.     uf(x[i]+N, y[i]);
  319.     if(uf(x[i])==uf(x[i]+N) || uf(y[i])==uf(y[i]+N)){
  320.       break;
  321.     }
  322.   }
  323.   wt_L(res);
  324.   wt_L('\n');
  325.   return 0;
  326. }
  327. // cLay version 20201123-1
  328.  
  329. // --- original code ---
  330. // int N, A[500][500];
  331. // int m, x[2d5], y[2d5], z[2d5];
  332. // {
  333. //   int res = 0;
  334. //   unionFind uf;
  335. //   rd(N,A(N,N));
  336. //   rep(i,N) rep(j,i+1,N) arrInsert(m, m, x, i, y, j, z, A[i][j]);
  337. //   sortA(m, z, x, y);
  338. //   uf.malloc(2*N,1);
  339. //   rep(i,m){
  340. //     res = z[i];
  341. //     uf(x[i], y[i]+N);
  342. //     uf(x[i]+N, y[i]);
  343. //     if(uf(x[i])==uf(x[i]+N) || uf(y[i])==uf(y[i]+N)) break;
  344. //   }
  345. //   wt(res);
  346. // }
  347.  
Time limit exceeded #stdin #stdout 5s 4468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EhCqpL
language:
C++ (gcc 8.3)
created:
3 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!