Overview

This problem asks us to determine whether \(N\) servers can be connected using \(M\) cables such that all servers can communicate with each other (i.e., the network is connected). To connect two servers, a cable with bandwidth at least equal to the sum of both servers’ communication loads is required.

Analysis

1. Required Number of Connections

To make all \(N\) servers connected, at least \(N-1\) cables are needed. Therefore, if the number of cables \(M\) is less than \(N-1\), the answer is immediately No.

2. What Configuration is Optimal?

Let \(A_i\) be the communication load of server \(i\). The required bandwidth to connect two servers \(u, v\) is \(A_u + A_v\). To make effective use of cables with limited bandwidth, the best strategy is to create connections with combinations that “minimize the required bandwidth \(A_u + A_v\) as much as possible.”

Let \(A_{min}\) be the value of the server with the minimum communication load. When any other server \(i\) must be connected somewhere, the connection destination that minimizes the load is \(A_{min}\). Therefore, considering a star graph configuration where all servers (except \(A_{min}\) itself) are directly connected to \(A_{min}\) gives us the spanning tree construction with the most relaxed conditions (requiring the minimum bandwidth).

In this case, the \(N-1\) required connection conditions are as follows: - \(A_{min} + A_i\) (where \(i\) ranges over all servers other than \(A_{min}\))

We sort these \(N-1\) values in ascending order and check whether cables satisfying each requirement can be selected from among the \(M\) available cables.

3. Greedy Determination

Let \(R = \{r_1, r_2, \ldots, r_{N-1}\}\) be the list of required bandwidths, and \(L = \{L_1, L_2, \ldots, L_M\}\) be the bandwidths of available cables. After sorting both in ascending order, we can determine the answer using a greedy approach (two pointers) that assigns the smallest cable \(L_j\) satisfying each requirement \(r_i\), processing requirements from smallest to largest.

Algorithm

1. If \(N=1\), the network is already connected, so output Yes and terminate.
2. If \(M < N-1\), it is physically impossible to make the network connected, so output No and terminate.
3. Sort the server communication loads \(A\) in ascending order. The minimum value is \(A[0]\).
4. Sort the cable bandwidths \(L\) in ascending order.
5. Create the list of required bandwidths (in practice, since \(A\) is sorted, \(A[0]+A[1], A[0]+A[2], \ldots, A[0]+A[N-1]\) are already in order).
6. Using two pointers, sequentially check whether a cable in \(L\) exists that satisfies each requirement \(A[0]+A[i]\).
7. If cables satisfying all requirements (\(N-1\) in total) are found, output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting the servers takes \(O(N \log N)\), and sorting the cables takes \(O(M \log M)\).
  • The subsequent determination (two pointers) takes \(O(N + M)\).
• Space complexity: \(O(N + M)\)
  • Memory is needed to store the input data.

Implementation Notes

• Corner case \(N=1\): Even with 0 cables, the network is already connected, so the answer is Yes.

• Fast I/O: Since \(N, M\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() or similar.

• Leveraging sorting: The requirements \(A[0]+A[i]\) are automatically in ascending order when \(A\) is sorted, so there is no need to sort them again.

  Source Code

import sys

# 問題の要約:
# N 台のサーバーがあり、それぞれの通信負荷は A_i である。
# M 本のケーブルがあり、それぞれの帯域幅は L_j である。
# サーバー u と v を接続するには、L_j >= A_u + A_v を満たすケーブルが必要。
# 各ケーブルは一度しか使えず、すべてのサーバーを連結にする（全域木を構成する）ことができるか判定する。

def solve():
    # 高速な入出力のために sys.stdin.read().split() を使用してすべての入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # サーバーの数 N とケーブルの本数 M
    N = int(input_data[0])
    M = int(input_data[1])
    
    # サーバーが1台だけの場合、すでに連結であるため常に "Yes"
    if N == 1:
        print("Yes")
        return
    
    # N 台のサーバーを連結にするためには、少なくとも N-1 本のケーブルが必要
    if M < N - 1:
        print("No")
        return
    
    # サーバーの通信負荷 A とケーブルの帯域幅 L をパースする
    # A: 各サーバーの通信負荷
    # L: 各ケーブルの帯域幅
    A = list(map(int, input_data[2:2+N]))
    L = list(map(int, input_data[2+N:2+N+M]))
    
    # 通信負荷の小さいサーバーを優先的に使うのが最適な戦略。
    # すべてのサーバーを、最も通信負荷が小さいサーバー (A_min) と直接接続する
    # 「スターグラフ」を構成するのが、必要な帯域幅を最小化する全域木の作り方である。
    # このとき必要な帯域幅のセットは {A_min + A_i | i は A_min 以外の各サーバー} となる。
    
    # 通信負荷 A を昇順にソートする (A[0] が最小負荷のサーバー)
    A.sort()
    # ケーブルの帯域幅 L を昇順にソートする
    L.sort()
    
    # A[0] と他の各サーバー A[1], A[2], ..., A[N-1] を接続するための N-1 個の要件を判定する。
    # 要件 A[0] + A[1], A[0] + A[2], ..., A[0] + A[N-1] はすでに昇順に並んでいる。
    
    # 貪欲法（2ポインタ）を用いて、利用可能なケーブルで要件を満たせるか確認する。
    req_idx = 1 # A[1] から A[N-1] までのサーバーとの接続を目指す
    a0 = A[0]
    
    for cable in L:
        if req_idx < N:
            # 現在のケーブルが現在の最小の要件 (a0 + A[req_idx]) を満たせるか確認
            if cable >= a0 + A[req_idx]:
                # 要件を満たせるなら、そのサーバーは接続済みとして次の要件へ
                req_idx += 1
        else:
            # すべてのサーバー (N-1 本の接続) がすでに満たされた場合
            break
            
    # 全域木に必要な N-1 本の接続がすべて確立できたかどうかを確認
    if req_idx == N:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.