結果

問題 No.1523 +/- Tree
ユーザー qwewe
提出日時 2025-05-14 13:06:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,103 bytes
コンパイル時間 643 ms
コンパイル使用メモリ 74,200 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-14 13:07:35
合計ジャッジ時間 3,167 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    // Use faster I/O operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int N_int; // N can be up to 2000, fits in int
    int K; // K can be up to N-1 <= 1999, fits in int
    std::cin >> N_int >> K;
    
    // Cast N to long long for calculations involving potentially large intermediate values, 
    // although with N=2000, standard int might suffice but long long is safer.
    long long N = N_int; 

    // Analyze the conditions:
    // Condition 1: Edge weights are integers, absolute value <= 10^9.
    // Condition 2: Sum of all edge weights is positive.
    // Condition 3: At least one simple path of length K exists.
    // Condition 4: All simple paths of length K have negative total weight.

    // Consider the case K=1.
    // Condition 4 implies any path of length 1 (i.e., any single edge) must have negative weight.
    // If all edge weights are negative, their sum must be negative.
    // This contradicts Condition 2, which requires the total sum to be positive.
    // Thus, no solution exists for K=1.
    if (K == 1) {
        std::cout << "No" << std::endl;
        return 0;
    }
    
    // Consider the path graph structure: vertices 1, 2, ..., N connected linearly.
    // Edges are (1, 2), (2, 3), ..., (N-1, N). Total N-1 edges.
    // This structure guarantees the existence of simple paths of length K for any 1 <= K <= N-1.
    // In a path graph, any simple path of length K must connect vertices i and i+K for some 1 <= i <= N-K.
    // The path consists of edges (i, i+1), (i+1, i+2), ..., (i+K-1, i+K).
    
    long long N_minus_1 = N - 1; // Total number of edges in the tree
    
    // Analyze the condition derived from path graph structure:
    // If N-1 is divisible by K, say N-1 = qK, then the path graph 1-2-...-N 
    // can be partitioned into q disjoint paths of length K.
    // Path 1: edges (1,2)...(K,K+1), starts at vertex 1.
    // Path 2: edges (K+1,K+2)...(2K,2K+1), starts at vertex K+1.
    // ...
    // Path q: edges ((q-1)K+1, (q-1)K+2)...(qK, qK+1=N), starts at vertex (q-1)K+1.
    // By Condition 4, each of these q paths must have a negative sum of weights.
    // The total sum of weights in the tree is the sum of weights of these q paths.
    // Since each path sum is negative, the total sum must also be negative.
    // This contradicts Condition 2, which requires the total sum of weights to be positive.
    // Therefore, if N-1 is divisible by K, no solution exists.
    if (N_minus_1 % K == 0) {
        std::cout << "No" << std::endl;
        return 0;
    }
    
    // If N-1 is not divisible by K, we can construct a solution using the path graph.
    // Print "Yes" as we are guaranteed to find a construction.
    std::cout << "Yes" << std::endl;
    
    // Calculate quotient q and remainder r for (N-1) / K.
    long long q = N_minus_1 / K; 
    long long r = N_minus_1 % K; // Remainder r satisfies 1 <= r <= K-1 since N-1 is not divisible by K.
    
    std::vector<long long> weights(N_minus_1); // Vector to store weights for the N-1 edges
    long long P, Q; // Positive integer values used to construct weights. Weights will be P or -Q.
    
    // We use a periodic assignment of weights based on the edge index modulo K.
    // Let the edge index be j+1 for the edge connecting vertices j+1 and j+2 (where j is 0-based index).
    // We consider the value (j+1) mod K.
    
    // Case 1: The remainder r satisfies 1 <= r <= K-2. 
    // Note that K >= 2, so K-2 >= 0. This case covers remainders strictly less than K-1.
    if (r <= K - 2) { 
        // Use the construction: P = q(K-r)+1, Q = r(q+1).
        // These values P, Q are derived to satisfy conditions. Both P and Q are positive integers.
        P = q * (K - r) + 1;
        Q = r * (q + 1);
         // Assign weights based on edge index modulo K
         for (int j = 0; j < N_minus_1; ++j) {
             long long edge_idx = j + 1; // Edges are indexed 1 to N-1
             // Calculate edge index modulo K. Map remainder 0 to K for consistency {1, ..., K}.
             long long mod_k = edge_idx % K; 
             if (mod_k == 0) mod_k = K; 
             
             // Assign weight P if edge index mod K falls into the first r classes {1, ..., r}
             if (mod_k >= 1 && mod_k <= r) {
                 weights[j] = P;
             } else { // Assign weight -Q if edge index mod K falls into the remaining classes {r+1, ..., K}
                 weights[j] = -Q;
             }
         }
    } 
    // Case 2: The remainder r is K-1. This is the only other possibility since 1 <= r <= K-1.
    else { // r == K - 1
        // Use the construction: P = q+1, Q = (K-1)(q+1)+1.
        // These values P, Q are derived to satisfy conditions. Both P and Q are positive integers.
        P = q + 1;
        // Use long long for intermediate calculation of Q for safety, though result should fit.
        Q = (long long)(K - 1) * (q + 1) + 1; 
         // Assign weights based on edge index modulo K
         for (int j = 0; j < N_minus_1; ++j) {
             long long edge_idx = j + 1; // Edges are indexed 1 to N-1
             // Calculate edge index modulo K. Map remainder 0 to K.
             long long mod_k = edge_idx % K;
             if (mod_k == 0) mod_k = K; 
             
             // Assign weight P if edge index mod K is in {1, ..., K-1}
             if (mod_k >= 1 && mod_k <= K - 1) { // This check is equivalent to mod_k != K
                 weights[j] = P;
             } else { // Assign weight -Q if edge index mod K is K (i.e., edge_idx is a multiple of K)
                 weights[j] = -Q;
             }
         }
    }

    // Output the edges of the constructed path graph 1-2-...-N with their calculated weights.
    // The i-th edge (0-based index i) connects vertex i+1 and i+2.
    for (int i = 0; i < N_minus_1; ++i) {
        // Output format requires: vertex_u vertex_v weight
        std::cout << i + 1 << " " << i + 2 << " " << weights[i] << "\n";
    }
    
    return 0;
}
0