fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "graph"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+19972207;
  49. const int maxn=1e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. // Khai báo các biến toàn cục
  72. int diss, numPair;
  73. int numNode;
  74. vector<pair<int, int>> edges;
  75. // Hết khai báo các biến toàn cục
  76.  
  77. void init(void) {
  78.     cin >> diss >> numPair;
  79. }
  80.  
  81. void print(void) {
  82.     cout << numNode << " " << edges.size() << "\n";
  83.     for (const pair<int, int> &e : edges) cout << e.fi << " " << e.se << "\n";
  84. }
  85.  
  86. namespace general {
  87.     bool check(void) {
  88.         return diss > 2;
  89.     }
  90.  
  91.     void createComponent(int x, int y) {
  92.         // Tạo đường đi P gồm diss cạnh (diss+1 đỉnh)
  93.         // P_1 -- P_2 -- ... -- P_{diss+1}. Khoảng cách P_1-P_{diss+1} là diss.
  94.         // P_1 là left_center, P_{diss+1} là right_center.
  95.  
  96.         int left_center = ++numNode;
  97.         int cur = left_center;
  98.         ff(i, 1, diss) {
  99.             int tmp = ++numNode;
  100.             edges.push_back({cur, tmp});
  101.             cur = tmp;
  102.         }
  103.         int right_center = cur;
  104.  
  105.         // Đính x lá vào left_center và y lá vào right_center
  106.         ff(i, 1, x) edges.push_back({left_center, ++numNode});
  107.         ff(i, 1, y) edges.push_back({right_center, ++numNode});
  108.  
  109.         // Tổng số đỉnh thêm: (diss + 1) + x + y
  110.         // Tổng số cạnh thêm: diss + x + y
  111.     }
  112.  
  113.     void solve(void) {
  114.         while (numPair > 0) {
  115.             // Số đỉnh cần cho 1 TPLT: (diss + 1) + x + y
  116.             int N_required_min = diss + 1 + 2; // (diss+1) + 1 + 1 (cho x=y=1)
  117.  
  118.             // Giới hạn số đỉnh còn lại
  119.             int N_remain = 1000 - numNode;
  120.             if (N_remain < N_required_min) break;
  121.  
  122.             // Giới hạn về số cạnh còn lại
  123.             int M_remain = 1000 - (int)edges.size();
  124.  
  125.             // Tìm t tối ưu (Cauchy) sao cho t*t <= numPair
  126.             int current_t = (int)sqrt(numPair);
  127.  
  128.             // Giới hạn t bởi số đỉnh: (diss + 1) + 2*t <= N_remain => 2*t <= N_remain - (diss + 1)
  129.             int limit_t_N = (N_remain - (diss + 1)) / 2;
  130.             if (limit_t_N < 1) limit_t_N = 1;
  131.  
  132.             // Giới hạn t bởi số cạnh: diss + 2*t <= M_remain => 2*t <= M_remain - diss
  133.             int limit_t_M = (M_remain - diss) / 2;
  134.             if (limit_t_M < 1) limit_t_M = 1;
  135.  
  136.             int limit_t = min(limit_t_N, limit_t_M);
  137.  
  138.             int t = min(current_t, limit_t);
  139.             if (t < 1) t = 1;
  140.  
  141.             int x, y;
  142.             if (t * t <= numPair) {
  143.                 x = t;
  144.                 y = t;
  145.             } else { // Trường hợp numPair rất nhỏ
  146.                 x = 1;
  147.                 y = numPair; // Sẽ xử lý giới hạn ngay dưới đây
  148.             }
  149.  
  150.             // Nếu x=t, y=t vượt quá giới hạn đỉnh/cạnh, ta phải dùng x và y khác
  151.             if (numNode + (diss + 1) + x + y > 1000 || edges.size() + diss + x + y > 1000) {
  152.                 // Ta phải dùng x=1 (tối thiểu), và y tối đa có thể
  153.                 x = 1;
  154.  
  155.                 // Giới hạn y bởi số đỉnh: (diss + 1) + 1 + y <= N_remain
  156.                 int limit_y_N = N_remain - (diss + 1) - 1;
  157.                 if (limit_y_N < 1) limit_y_N = 1;
  158.  
  159.                 // Giới hạn y bởi số cạnh: diss + 1 + y <= M_remain
  160.                 int limit_y_M = M_remain - diss - 1;
  161.                 if (limit_y_M < 1) limit_y_M = 1;
  162.  
  163.                 y = min({numPair, limit_y_N, limit_y_M});
  164.  
  165.                 if (y < 1) { // Không thể thêm bất kỳ cặp nào
  166.                     break;
  167.                 }
  168.             }
  169.  
  170.             // Nếu x*y > numPair (chỉ xảy ra khi ta dùng limit_t > current_t, hoặc x=1, y=numPair)
  171.             if (x * y > numPair) {
  172.                 // Nếu x=t, y=t. Ta phải tìm x và y sao cho x*y <= numPair, x+y nhỏ nhất
  173.                 x = (int)sqrt(numPair);
  174.                 y = numPair / x;
  175.  
  176.                 // Kiểm tra lại giới hạn
  177.                 if (numNode + (diss + 1) + x + y > 1000 || edges.size() + diss + x + y > 1000) {
  178.                     // Nếu vẫn vượt giới hạn, dùng x=1, y=numPair giới hạn bởi 1000
  179.                     x = 1;
  180.                     int limit_y = min({1000 - numNode - (diss + 2), 1000 - (int)edges.size() - diss - 1});
  181.                     y = min(numPair, limit_y);
  182.                 }
  183.             }
  184.  
  185.             if (x > 0 && y > 0) {
  186.                 createComponent(x, y);
  187.                 numPair -= x * y;
  188.             } else {
  189.                 break;
  190.             }
  191.         }
  192.     }
  193. }
  194.  
  195. namespace special {
  196.     bool check(void) {
  197.         return diss == 2;
  198.     }
  199.  
  200.     void createComponent(int t) {
  201.         // Tạo ra TPLT có 1 đỉnh u nối với t đỉnh khác (v1, ..., vt).
  202.         // Khoảng cách giữa các cặp (vi, vj) là 2. Có t*(t-1)/2 cặp.
  203.  
  204.         int u = ++numNode;
  205.         ff(i, 1, t) edges.push_back({u, ++numNode});
  206.  
  207.         // Tổng số đỉnh thêm: 1 + t
  208.         // Tổng số cạnh thêm: t
  209.     }
  210.  
  211.     void solve(void) { 
  212.         while (numPair > 0) {
  213.             // Tìm t tối ưu: t*(t-1)/2 <= numPair
  214.             int t = 2;
  215.             while ((ll)(t + 1) * t / 2 <= numPair) t++;
  216.             t--;
  217.  
  218.             // Số đỉnh cần cho 1 TPLT: 1 + t
  219.             int N_remain = 1000 - numNode;
  220.             if (N_remain < 1 + 2) break; // Cần ít nhất 3 đỉnh (t=2)
  221.  
  222.             // Giới hạn về số cạnh còn lại
  223.             int M_remain = 1000 - (int)edges.size();
  224.  
  225.             // Giới hạn t bởi số đỉnh: 1 + t <= N_remain
  226.             int limit_t_N = N_remain - 1;
  227.  
  228.             // Giới hạn t bởi số cạnh: t <= M_remain
  229.             int limit_t_M = M_remain;
  230.  
  231.             int limit_t = min(limit_t_N, limit_t_M);
  232.  
  233.             t = min(t, limit_t);
  234.             if (t < 2) t = 2; // Cần t >= 2 để có cặp đỉnh khoảng cách 2
  235.  
  236.             // Nếu t*(t-1)/2 > numPair (chỉ xảy ra khi ta dùng limit_t > t_Cauchy)
  237.             if ((ll)t * (t - 1) / 2 > numPair) {
  238.                 // Ta phải tìm t sao cho t*(t-1)/2 <= numPair và t nhỏ nhất
  239.                 t = 2;
  240.                 while ((ll)(t + 1) * t / 2 <= numPair) t++;
  241.                 t--;
  242.                 // Sau đó giới hạn lại theo limit_t
  243.                 t = min(t, limit_t);
  244.                 if (t < 2) t = 2;
  245.             }
  246.  
  247.             // Nếu t vẫn quá nhỏ (t=1) thì không tạo được cặp nào
  248.             if (t < 2) break;
  249.  
  250.             ll pairs_created = (ll)t * (t - 1) / 2;
  251.             if (pairs_created > 0) {
  252.                 createComponent(t);
  253.                 numPair -= pairs_created;
  254.             } else {
  255.                 break;
  256.             }
  257.         }
  258.     }
  259. }
  260.  
  261. void process(void) {
  262.     if (general::check()) {
  263.         general::solve();
  264.     } else if (special::check()) {
  265.         special::solve();
  266.     }
  267. }
  268.  
  269. signed main()
  270. {
  271.     rf();
  272.     init();
  273.     process();
  274.     print();
  275.     //re; // Bỏ re; để chương trình kết thúc bình thường
  276.     return 0;
  277. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
2 1
stdout
copy 
3 2
1 2
1 3
https://ideone.com/RpiiLS
language:
C++14 (gcc 8.3)
created:
1 day 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!