JaviGr

Untitled

Jul 3rd, 2018
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int,int> ii;
  5. typedef pair<ii,int> data;
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9.  
  10. const int N = 4e5 + 5;
  11.  
  12. int n, d, k;
  13. vector<ii> edges;
  14. priority_queue<data> pq;
  15. int deg[N], far[N];
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(false);
  19.     cin >> n >> d >> k;
  20.     if (n <= d) return cout << "NO\n",0;
  21.     for (int i = 1; i <= d; ++i) {
  22.         deg[i]++, deg[i + 1]++;
  23.         edges.pb(ii(i, i + 1));
  24.         far[i] = max(i - 1, d + 1 - i);
  25.     }
  26.     far[d + 1] = d;
  27.     int tot = d + 1;
  28.     for (int i = 1; i <= d + 1; ++i) {
  29.         if (deg[i] < k && far[i] < d) pq.push(data(ii(far[i], deg[i]), i));
  30.     }
  31.     while (!pq.empty()) {
  32.         if (tot == n) break;
  33.         int u = pq.top().se; pq.pop();
  34.         tot++; edges.pb(ii(u, tot));
  35.         deg[u]++; if (deg[u] < k) pq.push(data(ii(far[u], deg[u]), u));
  36.         deg[tot]++; far[tot] = far[u] + 1;
  37.         if (deg[tot] < k && far[tot] < d) pq.push(data(ii(far[tot], deg[tot]), tot));
  38.     }
  39.     if (tot < n) return cout << "NO\n",0;
  40.     cout << "YES\n";
  41.     for (auto edge : edges) {
  42.         cout << edge.fi << ' ' << edge.se << '\n';
  43.     }
  44. }
Add Comment
Please, Sign In to add comment