fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long n,m,t;
  5. bool taken[100][100];
  6. long long val[1000006];
  7.  
  8. bool cmp(vector<int> L,vector<int> R) {
  9.     if(L.size()==R.size())
  10.         return L<R;
  11.     else
  12.         return L.size()<R.size();
  13. }
  14.  
  15. int main() {
  16.  
  17. //    freopen("o.txt","w",stdout);
  18.  
  19.     cin>>t;
  20.     while(t--) {
  21.         scanf("%lld %lld",&n,&m);
  22.         memset(taken,0,sizeof(taken));
  23.  
  24.         if(n==1) {
  25.             if(m==0)
  26.                 puts("0");
  27.             else if(m==1)
  28.                 puts("1");
  29.             else
  30.                 puts("-1");
  31.  
  32.             continue;
  33.         }
  34.  
  35.         if(m>=n-1 && m<= n*(n-1)/2+n) {
  36.  
  37.             if(m-(n-1)>n) {
  38.  
  39.                 m=m-(n-1)-n;
  40.                 val[1]=val[n]=2;
  41.                 for(int i=2; i<n; i++)
  42.                     val[i]=3;
  43.  
  44.                 for(int i=1; i<n; i++) {
  45.                     taken[i][i+1]=taken[i+1][i]=1;
  46.                 }
  47.  
  48.                 while(m--) {
  49.                     int mn=INT_MAX;
  50.                     vector<pair<int,int> > min_edges;
  51.  
  52.                     for(int i=1; i<=n; i++)
  53.                         for(int j=i+1; j<=n; j++) {
  54.  
  55.                             if(taken[i][j]==0 && max(val[i]+1,val[j]+1)<mn) {
  56.                                 mn=max(val[i]+1,val[j]+1);
  57.                                 min_edges.clear();
  58.                             }
  59.  
  60.                             if(taken[i][j]==0 && max(val[i]+1,val[j]+1)==mn) {
  61.                                 min_edges.push_back({i,j});
  62.                             }
  63.  
  64.                         }
  65.  
  66.                     vector<vector<int> > pile;
  67.                     vector<vector<int> > pile2;
  68.  
  69.                     int mn2=INT_MAX;
  70.                     int indx=0;
  71.  
  72.                     for(auto von: min_edges) {
  73.                         vector<int> boom;
  74.  
  75.                         for(int i=1; i<=n; i++)
  76.                             if(i!=von.first && i!=von.second && (taken[i][von.first]==0 || taken[von.first][i]==0 )) {
  77.                                 if(max(val[i],val[von.first]+1)!=max(val[i],val[von.first])) {
  78.                                     boom.push_back(max(val[i],val[von.first]+1));
  79.                                 }
  80.                             }
  81.  
  82.                         for(int i=1; i<=n; i++)
  83.                             if(i!=von.second && i!=von.first && (taken[i][von.second]==0 || taken[von.second][i]==0)) {
  84.                                 if(max(val[i],val[von.second]+1)!=max(val[i],val[von.second])) {
  85.                                     boom.push_back(max(val[i],val[von.second]+1));
  86.                                 }
  87.                             }
  88.  
  89.  
  90.                         sort(boom.begin(),boom.end());
  91.  
  92.                         if(boom.size()==0) {
  93.                             auto pr=von;
  94.                             taken[pr.first][pr.second]=taken[pr.second][pr.first]=1;
  95.                             val[pr.first]++;
  96.                             val[pr.second]++;
  97.                             goto jump;
  98.                         }
  99.  
  100.                         pile.push_back(boom);
  101.  
  102.                         if(mn2>boom.back()) {
  103.                             mn2=boom.back();
  104.                             pile2.clear();
  105.                         }
  106.  
  107.                         if(mn2==boom.back()) {
  108.                             pile2.push_back(boom);
  109.                         }
  110.  
  111.                         indx++;
  112.  
  113.                     }
  114.  
  115.                     sort(pile2.begin(),pile2.end(),cmp);
  116.  
  117.                     for(int i=0; i<pile.size(); i++)
  118.                         if(pile2[0]==pile[i]) {
  119.                             auto pr=min_edges[i];
  120.                             taken[pr.first][pr.second]=taken[pr.second][pr.first]=1;
  121.                             val[pr.first]++;
  122.                             val[pr.second]++;
  123.                             break;
  124.                         }
  125.  
  126. jump:
  127.                     ;
  128.  
  129.                 }
  130.  
  131.                 long long mx=LLONG_MIN;
  132.                 for(int i=1; i<=n; i++)
  133.                     if(val[i]>mx) {
  134.                         mx=val[i];
  135.                     }
  136.  
  137.                 printf("%lld\n",mx);
  138.  
  139.             } else {
  140.  
  141.                 if(m-(n-1)==0) {
  142.                     if(n==2)
  143.                         puts("1");
  144.                     else
  145.                         puts("2");
  146.                 } else if(m-(n-1)-2>0)
  147.                     puts("3");
  148.                 else
  149.                     puts("2");
  150.  
  151.             }
  152.  
  153.  
  154.         } else {
  155.             puts("-1");
  156.         }
  157.  
  158.  
  159.     }
  160.  
  161.  
  162.     return 0;
  163. }
  164.  
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ahag0p
language:
C++14 (gcc 8.3)
created:
4 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!