Advertisement
Korotkodul

E_easy?

Dec 31st, 2021 (edited)
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. using namespace std;
  12. using ll = long long;
  13. using ld = long double;
  14. void cv(vector <int> &v){
  15.     for (auto x: v) cout<<x<<' ';
  16.     cout<<"\n";
  17. }
  18.  
  19. void cvv(vector <vector <int> > &v){
  20.     for (auto x: v) cv(x);
  21.     cout<<"\n";
  22. }
  23. int n, mn, mx;
  24. vector <vector <int> > G;
  25. vector <pii> Edge;
  26. void cG(){
  27.     for (int i = 0; i < n;++i){
  28.         cout<<"("<<i<<"): ";
  29.         cv(G[i]);
  30.     }
  31. }
  32.  
  33. void cEdge(){
  34.     cout<<Edge.size()<<"\n";
  35.     for (auto x: Edge){
  36.         cout<<x.first+1<<' '<<x.second+1<<"\n";
  37.     }
  38. }
  39.  
  40. vector <int> lvl; //степени вершин
  41.  
  42. bool cmp(int a, int b){
  43.     return lvl[a] > lvl[b];
  44. }
  45.  
  46. vector <int> vrt;
  47.  
  48. vector <vector <int> > comp;
  49.  
  50.  
  51. int main()
  52. {
  53.     ios::sync_with_stdio(0);
  54.     cin.tie(0);
  55.     cout.tie(0);
  56.     cin>>n>>mx>>mn;
  57.     G.resize(n);
  58.     lvl.assign(n, 0);
  59.     for (int i = 0; i < n; ++i){
  60.         vrt.push_back(i);
  61.         if (G[i].size() == mn) continue;
  62.         for (int j = 0; j < n && j != i; ++j){
  63.             if (G[j].size() >= mn) continue;
  64.             if (find(G[i].begin(), G[i].end(), j) == G[i].end() ){
  65.                 G[i].push_back(j);
  66.                 G[j].push_back(i);
  67.                 Edge.push_back({min(i, j), max(i, j)});
  68.                 lvl[i]++;
  69.                 lvl[j]++;
  70.             }
  71.             if (G[i].size() == mn){
  72.                 break;
  73.             }
  74.         }
  75.     }
  76.     sort(vrt.begin(), vrt.end(), cmp);
  77.     //cout<<"graph\n";
  78.     //cG();
  79.     //cv(vrt);
  80.     vector <int> v;
  81.     for (int i = 0; i < n / (mn + 1); ++i){
  82.  
  83.         for (int j = (mn + 1) * i; j < (i + 1) * (mn + 1); ++j){
  84.             //par[j] = i;
  85.             v.push_back(j);
  86.         }
  87.         comp.push_back(v);
  88.         v.clear();
  89.     }
  90.     for (int i = (n / (mn + 1)) * (mn + 1); i < n; ++i ){
  91.         //par[i] = (n / (mn + 1)) * (mn + 1);
  92.         v.push_back(i);
  93.         //cout<<"i = "<<i<<"\n";
  94.     }
  95.  
  96.     if (!v.empty()){
  97.         comp.push_back(v);
  98.  
  99.         v.clear();
  100.         for (int i = 0; i < comp[comp.size() - 1].size(); ++i){
  101.             int u = comp[comp.size() - 1][i];
  102.             if (lvl[u] >= mn) continue;
  103.             sort(vrt.begin(), vrt.end(), cmp);
  104.             for (int j = 0; j < n;++j){
  105.                 if (find(G[u].begin(), G[u].end(), vrt[j]) != G[u].end()){
  106.                     continue;
  107.                 }
  108.                 else if (lvl[vrt[j]] == mx) continue;
  109.                 else if (vrt[j] == u) continue;
  110.                 G[u].push_back(vrt[j]);
  111.                 G[vrt[j]].push_back(u);
  112.                 Edge.push_back({min(u, vrt[j]), max(u, vrt[j])});
  113.                 lvl[u]++;
  114.                 lvl[vrt[j]]++;
  115.                 if (lvl[u] == mn) break;
  116.             }
  117.         }
  118.     }
  119.     /*cout<<"comp\n";
  120.     cvv(comp);
  121.     cout<<"last comp\n";
  122.     cv(comp[comp.size() - 1]);*/
  123.     sort(vrt.begin(), vrt.end(), cmp);
  124.     int mx_v = vrt[0];
  125.     if (lvl[mx_v] < mx){
  126.         for (int i = 0; i < n; ++i){
  127.             if (vrt[i] == mx_v) continue;
  128.             else if (find(G[mx_v].begin(), G[mx_v].end(), vrt[i]) != G[mx_v].end()) continue;
  129.             else if (lvl[vrt[i]] == mx) continue;
  130.             G[mx_v].push_back(vrt[i]);
  131.             G[vrt[i]].push_back(mx_v);
  132.             lvl[mx_v]++;
  133.             lvl[vrt[i]]++;
  134.             Edge.push_back({min(mx_v, vrt[i]), max(mx_v, vrt[i])});
  135.             if (lvl[mx_v] == mx) {
  136.                 break;
  137.             }
  138.         }
  139.     }
  140.     //cout<<"graph\n";
  141.     //cG();
  142.     cEdge();
  143. }
  144. /*
  145. 15 4 3
  146.  
  147. 17 7 5
  148. */
  149.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement