Beingamanforever

ICPC-B

Nov 16th, 2024
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. /**
  2.  *    author:  compounding
  3.  *    created: 2024-11-16 18:33:28
  4.  **/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
  8. #define NeedForSpeed                  \
  9.     ios_base::sync_with_stdio(false); \
  10.     cin.tie(NULL);                    \
  11.     cout.tie(NULL);
  12. #define int long long
  13. #define all(x) (x).begin(), (x).end()
  14. typedef vector<int> vi;
  15. typedef vector<bool> vb;
  16. typedef vector<vi> vvi;
  17. typedef vector<pair<int, int>> vpi;
  18. #define f first
  19. #define s second
  20. #define yes cout << "YES" << endl
  21. #define no cout << "NO" << endl
  22. #define endl "\n"
  23. const int mod = 1000000007;
  24. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  25. void solve()
  26. {
  27.     int n, d, l;
  28.     cin >> n >> d >> l;
  29.     // edge cases
  30.     if (n <= l)
  31.     {
  32.         cout << -1 << endl;
  33.         return;
  34.     }
  35.     vector<pair<int, int>> edges;
  36.     // straight line
  37.     for (int i = 1; i <= d; i++)
  38.     {
  39.         edges.push_back({i, i + 1});
  40.     }
  41.     int mid = (d + 2) / 2;
  42.     // all leaves in mid
  43.     int leaves_left = l - 2;
  44.     int curnode = d + 2;
  45.     // leaves lagate hain
  46.     queue<pair<int, int>> q;
  47.     for (; curnode <= n && (leaves_left > 0); curnode++)
  48.     {
  49.         edges.push_back({mid, curnode});
  50.         leaves_left--;
  51.         q.push({curnode, 1});
  52.     }
  53.     // step 2
  54.     if (curnode > n && leaves_left > 0)
  55.     {
  56.         cout << -1 << endl;
  57.         return;
  58.     }
  59.     if (leaves_left == 0)
  60.     {
  61.         for (auto edge : edges)
  62.         {
  63.             cout << edge.first << " " << edge.second << endl;
  64.         }
  65.         return;
  66.     }
  67.     else
  68.     {
  69.         // leaves fullfilled, but not n (total number of nodes)
  70.         int buffer = mid - 1;
  71.         while (!q.empty())
  72.         {
  73.             auto [node, dist] = q.front();
  74.             q.pop();
  75.             if (dist + 1 <= buffer)
  76.             {
  77.                 edges.push_back({node, curnode});
  78.                 q.push({curnode, dist + 1});
  79.                 curnode++;
  80.             }
  81.         }
  82.         // as all nodes have not been used
  83.         if (curnode <= n)
  84.         {
  85.             cout << -1 << endl;
  86.             return;
  87.         }
  88.         else
  89.         {
  90.             for (auto edge : edges)
  91.             {
  92.                 cout << edge.first << " " << edge.second << endl;
  93.             }
  94.             // cout << "geeks";
  95.         }
  96.     }
  97.     return;
  98. }
  99.  
  100. signed main()
  101. {
  102.     NeedForSpeed;
  103.     int t = 1;
  104.     cin >> t;
  105.     while (t--)
  106.     {
  107.         solve();
  108.     }
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment