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); // Only possible case for 2 nodes
  11.  
  12.     // For diameter 1, tree must be a star with n-1 leaves
  13.     if (d == 1) return (l == n-1);
  14.  
  15.     // For diameter 2, we need at least 2 leaves and at most n-1 leaves
  16.     if (d == 2) return (l >= 2 && l <= n-1);
  17.  
  18.     // For general case with diameter d
  19.     // We need at least d+1 nodes for the main path
  20.     int nodesInPath = d + 1;
  21.     if (nodesInPath > n) return false;
  22.  
  23.     // Maximum possible leaves is n - (d-1)
  24.     // Because we need at least d-1 internal nodes for the path
  25.     int maxPossibleLeaves = n - (d-1);
  26.  
  27.     // Minimum leaves is 2 (at the ends of the diameter path)
  28.     return (l >= 2 && l <= maxPossibleLeaves);
  29. }
  30.  
  31. void constructTree(int n, int d, int l) {
  32.     if (!canConstructTree(n, d, l)) {
  33.         cout << -1 << "\n";
  34.         return;
  35.     }
  36.  
  37.     // Case 1: Diameter 1 (Star-shaped tree)
  38.     if (d == 1) {
  39.         for (int i = 2; i <= n; i++) {
  40.             cout << "1 " << i << "\n";
  41.         }
  42.         return;
  43.     }
  44.  
  45.     // Case 2: Diameter 2 (Tree with one non-leaf node and center node)
  46.     if (d == 2) {
  47.         int center = 1;
  48.         int nonLeafNode = 2;
  49.  
  50.         // Connect one non-leaf node to center
  51.         cout << center << " " << nonLeafNode << "\n";
  52.  
  53.         // Distribute remaining nodes as leaves between center and non-leaf node
  54.         int remainingLeaves = l;
  55.         int currentNode = 3;
  56.  
  57.         // Connect leaves to center
  58.         while (currentNode <= n && remainingLeaves > 1) {
  59.             cout << center << " " << currentNode << "\n";
  60.             currentNode++;
  61.             remainingLeaves--;
  62.         }
  63.  
  64.         // Connect remaining leaves to non-leaf node
  65.         while (currentNode <= n) {
  66.             cout << nonLeafNode << " " << currentNode << "\n";
  67.             currentNode++;
  68.         }
  69.         return;
  70.     }
  71.  
  72.     // Case 3: General case (d > 2)
  73.     // First create the diameter path
  74.     for (int i = 1; i <= d; i++) {
  75.         cout << i << " " << i + 1 << "\n";
  76.     }
  77.  
  78.     int currentNode = d + 2;
  79.     int remainingLeaves = l - 2;  // We already have 2 leaves at the ends
  80.  
  81.     // Add remaining leaves, distributing them between endpoints
  82.     while (currentNode <= n && remainingLeaves > 0) {
  83.         if (remainingLeaves > 0) {
  84.             cout << "1 " << currentNode << "\n";
  85.             remainingLeaves--;
  86.             currentNode++;
  87.         }
  88.         if (remainingLeaves > 0 && currentNode <= n) {
  89.             cout << d + 1 << " " << currentNode << "\n";
  90.             remainingLeaves--;
  91.             currentNode++;
  92.         }
  93.     }
  94.  
  95.     // If we have any remaining nodes, attach them to middle nodes
  96.     int middleNode = 2;  // Start attaching to second node of path
  97.     while (currentNode <= n) {
  98.         cout << middleNode << " " << currentNode << "\n";
  99.         currentNode++;
  100.         middleNode = middleNode % d + 1;  // Cycle through middle nodes
  101.     }
  102. }
  103.  
  104. int main() {
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(nullptr);
  107.  
  108.     int t;
  109.     cin >> t;
  110.  
  111.     while (t--) {
  112.         int n, d, l;
  113.         cin >> n >> d >> l;
  114.         constructTree(n, d, l);
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
2
3 2 3
6 3 4
stdout
copy 
-1
1 2
2 3
3 4
1 5
4 6
https://ideone.com/q0WoxG
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!