fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5.  
  6. int numpair , diss;
  7. int numnode;
  8. vector<pair<int,int>>edges;
  9.  
  10. void init(){
  11.     cin >> diss >> numpair;
  12. }
  13.  
  14. void print(){
  15.     cout << numnode << " " << edges.size() << '\n';
  16.     for(auto &e : edges) cout << e.fi <<  " " << e.se << '\n';
  17. }
  18.  
  19. namespace general{
  20.     bool check(){
  21.         return diss > 2;
  22.     }
  23.     void creatcomponent(int x , int y){
  24.         int left=++numnode;
  25.         int cur = left;
  26.         for(int i=0;i<diss-2;i++){
  27.             int tmp=++numnode;
  28.             edges.emplace_back(cur,tmp);
  29.             cur=tmp;
  30.         }
  31.         int right = cur;
  32.         for(int i=1;i<x;i++) edges.emplace_back(left,++numnode);
  33.         for(int i=1;i<y;i++) edges.emplace_back(right,++numnode);
  34.     }
  35.     void solve(){
  36.         while(numpair>0){
  37.             int t=1;
  38.             while((t+1)*(t+1)<=numpair) t++;
  39.             creatcomponent(t,t);
  40.             numpair-=t*t;
  41.         }
  42.     }
  43. }
  44. namespace special{
  45.     bool check(){
  46.         return diss==2;
  47.     }
  48.     void creatcomponent(int t){
  49.         int center=++numnode;
  50.         for(int i=0;i<t;i++){
  51.             int leaf=++numnode;
  52.             edges.emplace_back(center,leaf);
  53.         }
  54.     }
  55.     void solve(){
  56.         while(numpair>0){
  57.             int t=2;
  58.             while((t+1)*t/2<=numpair) t++;
  59.             creatcomponent(t);
  60.             numpair-=t*(t-1)/2;
  61.         }
  62.     }
  63. }
  64.  
  65. void process(){
  66.     if(general::check()) general::solve();
  67.     if(special::check()) special::solve();
  68. }
  69.  
  70. int main(){
  71.     ios_base::sync_with_stdio(0);
  72.     cin.tie(0);
  73.     cout.tie(0);
  74.     freopen("graph.inp","r",stdin);
  75.     freopen("graph.out","w",stdout);
  76.     init();
  77.     process();
  78.     print();
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/04XT4R
language:
C++14 (gcc 8.3)
created:
7 days 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!