fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool canConstructTree(int n, int d, int l) {
  5.     // Basic validation
  6.     if (l < 2 || l > n - (d - 1)) return false;  // Invalid number of leaves
  7.     if (d >= n) return false; // Diameter must be less than the number of nodes
  8.  
  9.     // Special cases
  10.     if (n == 2) return (d == 1 && l == 2);
  11.     if (d == 1) return (l == n-1);
  12.     if (d == 2) return (l >= 2 && l <= n-1);
  13.  
  14.     // For general case
  15.     return (l >= 2 && l <= n - (d-1));
  16. }
  17.  
  18. void constructTree(int n, int d, int l) {
  19.     if (!canConstructTree(n, d, l)) {
  20.         cout << -1 << "\n";
  21.         return;
  22.     }
  23.  
  24.     // Case 1: Diameter 1 (Star-shaped tree)
  25.     if (d == 1) {
  26.         for (int i = 2; i <= n; i++) {
  27.             cout << "1 " << i << "\n";
  28.         }
  29.         return;
  30.     }
  31.  
  32.     // Case 2: Diameter 2
  33.     if (d == 2) {
  34.         int center = 1;
  35.         int nonLeafNode = 2;
  36.  
  37.         cout << center << " " << nonLeafNode << "\n";
  38.  
  39.         // Add leaves to both nodes
  40.         int currentNode = 3;
  41.         int remainingLeaves = l;
  42.  
  43.         // First attach to center
  44.         while (currentNode <= n && remainingLeaves > 1) {
  45.             cout << center << " " << currentNode << "\n";
  46.             currentNode++;
  47.             remainingLeaves--;
  48.         }
  49.  
  50.         // Then to non-leaf node
  51.         while (currentNode <= n) {
  52.             cout << nonLeafNode << " " << currentNode << "\n";
  53.             currentNode++;
  54.         }
  55.         return;
  56.     }
  57.  
  58.     // General case (d > 2)
  59.     // First create a spine of length d-1
  60.     for (int i = 1; i < d; i++) {
  61.         cout << i << " " << i + 1 << "\n";
  62.     }
  63.  
  64.     int currentNode = d + 1;
  65.     int remainingLeaves = l - 1;  // Reserve one leaf for later
  66.  
  67.     // Add remaining leaves to spine nodes (except last node)
  68.     for (int i = 1; i < d && currentNode < n && remainingLeaves > 0; i++) {
  69.         // Add leaves to each spine node
  70.         if (i == 1 || i == d-1) {  // For first and second-last nodes
  71.             while (currentNode < n && remainingLeaves > 0) {
  72.                 cout << i << " " << currentNode << "\n";
  73.                 currentNode++;
  74.                 remainingLeaves--;
  75.                 if (i == 1 && remainingLeaves == 0) break;  // Ensure we save one leaf
  76.             }
  77.         }
  78.     }
  79.  
  80.     // Add any remaining internal nodes
  81.     for (int i = 2; i < d-1 && currentNode < n; i++) {
  82.         cout << i << " " << currentNode << "\n";
  83.         currentNode++;
  84.     }
  85.  
  86.     // Finally add the last node to complete the diameter
  87.     if (currentNode <= n) {
  88.         cout << d-1 << " " << currentNode << "\n";
  89.     }
  90. }
  91.  
  92. int main() {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(nullptr);
  95.  
  96.     int t;
  97.     cin >> t;
  98.  
  99.     while (t--) {
  100.         int n, d, l;
  101.         cin >> n >> d >> l;
  102.         constructTree(n, d, l);
  103.     }
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
2
3 2 3
6 3 3
stdout
copy 
-1
1 2
2 3
1 4
1 5
2 6
https://ideone.com/Ac3bwn
language:
C++ (gcc 8.3)
created:
5 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!