#104973 (C++14) No.466 ジオラマ

提出ソース

結果

問題	No.466 ジオラマ
ユーザー	🍡yurahuna
提出日時	2016-07-19 18:49:57
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	28 ms / 2,000 ms
コード長	2,442 bytes
コンパイル時間	1,800 ms
コンパイル使用メモリ	173,388 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-05-07 15:14:34
合計ジャッジ時間	5,080 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	15 ms 6,940 KB
testcase_07	AC	9 ms 6,940 KB
testcase_08	AC	20 ms 6,944 KB
testcase_09	AC	13 ms 6,944 KB
testcase_10	AC	15 ms 6,940 KB
testcase_11	AC	12 ms 6,944 KB
testcase_12	AC	17 ms 6,944 KB
testcase_13	AC	9 ms 6,940 KB
testcase_14	AC	8 ms 6,944 KB
testcase_15	AC	11 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	9 ms 6,940 KB
testcase_18	AC	10 ms 6,944 KB
testcase_19	AC	11 ms 6,940 KB
testcase_20	AC	11 ms 6,940 KB
testcase_21	AC	10 ms 6,940 KB
testcase_22	AC	15 ms 6,944 KB
testcase_23	AC	10 ms 6,944 KB
testcase_24	AC	17 ms 6,944 KB
testcase_25	AC	18 ms 6,944 KB
testcase_26	AC	10 ms 6,944 KB
testcase_27	AC	19 ms 6,944 KB
testcase_28	AC	14 ms 6,940 KB
testcase_29	AC	17 ms 6,940 KB
testcase_30	AC	13 ms 6,944 KB
testcase_31	AC	13 ms 6,944 KB
testcase_32	AC	13 ms 6,940 KB
testcase_33	AC	11 ms 6,940 KB
testcase_34	AC	13 ms 6,944 KB
testcase_35	AC	11 ms 6,944 KB
testcase_36	AC	7 ms 6,940 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	9 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	13 ms 6,940 KB
testcase_41	AC	1 ms 6,944 KB
testcase_42	AC	11 ms 6,944 KB
testcase_43	AC	2 ms 6,944 KB
testcase_44	AC	10 ms 6,944 KB
testcase_45	AC	2 ms 6,944 KB
testcase_46	AC	5 ms 6,944 KB
testcase_47	AC	1 ms 6,940 KB
testcase_48	AC	14 ms 6,944 KB
testcase_49	AC	2 ms 6,940 KB
testcase_50	AC	13 ms 6,940 KB
testcase_51	AC	1 ms 6,944 KB
testcase_52	AC	12 ms 6,940 KB
testcase_53	AC	1 ms 6,940 KB
testcase_54	AC	12 ms 6,940 KB
testcase_55	AC	2 ms 6,940 KB
testcase_56	AC	4 ms 6,940 KB
testcase_57	AC	1 ms 6,940 KB
testcase_58	AC	3 ms 6,940 KB
testcase_59	AC	1 ms 6,940 KB
testcase_60	AC	6 ms 6,944 KB
testcase_61	AC	1 ms 6,940 KB
testcase_62	AC	5 ms 6,940 KB
testcase_63	AC	1 ms 6,944 KB
testcase_64	AC	3 ms 6,940 KB
testcase_65	AC	1 ms 6,940 KB
testcase_66	AC	15 ms 6,940 KB
testcase_67	AC	1 ms 6,940 KB
testcase_68	AC	11 ms 6,944 KB
testcase_69	AC	1 ms 6,940 KB
testcase_70	AC	9 ms 6,944 KB
testcase_71	AC	1 ms 6,940 KB
testcase_72	AC	7 ms 6,944 KB
testcase_73	AC	2 ms 6,944 KB
testcase_74	AC	13 ms 6,940 KB
testcase_75	AC	2 ms 6,940 KB
testcase_76	AC	2 ms 6,940 KB
testcase_77	AC	2 ms 6,940 KB
testcase_78	AC	2 ms 6,944 KB
testcase_79	AC	2 ms 6,944 KB
testcase_80	AC	1 ms 6,944 KB
testcase_81	AC	1 ms 6,944 KB
testcase_82	AC	1 ms 6,944 KB
testcase_83	AC	1 ms 6,944 KB
testcase_84	AC	14 ms 6,940 KB
testcase_85	AC	28 ms 6,940 KB
testcase_86	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int N = A + B - C;                  // 村の個数
    int M = N - 1;                      // 辺の本数の最小値
    if (C == 0)             M = N - 2;  // 非連結になるとき
    if (A == C && B == C)   M = N;      // 閉路になるとき

    // 村が2個未満 or 辺の本数の最小値が D より大きい ならば、条件を満たす組はない
    if (N < 2 || M > D) {
        cout << -1 << endl;
        return 0;
    }

    vector<P> edges;    // 水路を格納しておくやつ
    if (A == C && B == C) {
        // 閉路になるとき
        // (スペシャルジャッジ検証のためループを逆順にする)
        rrep(i, N) edges.emplace_back(i, (i + 1) % N);
    } else {
        // 閉路になるとき以外
        int id = 2; // 村0, 1の次の2から番号を振っていく

        // (スペシャルジャッジ検証のためBからやっている)
        // 村1からのみ水が流れる村は、村1を除くと B-C-1個
        rep(i, B - C - 1) {
            edges.emplace_back(P(1, id));
            id++;
        }

        // 村0からのみ水が流れる村は、村0を除くと A-C-1個
        rep(i, A - C - 1) {
            edges.emplace_back(P(0, id));
            id++;
        }

        // 村0と村1の両方から水が流れる村
        if (C > 0) {
            int par;
            if (C == A) {
                edges.emplace_back(P(1, 0));
                par = 0;
            }
            else if (C == B) {
                edges.emplace_back(P(0, 1));
                par = 1;
            }
            else {
                edges.emplace_back(P(0, id));
                edges.emplace_back(P(1, id));
                par = id++;
            }
            rep2(i, id, N) {
                edges.emplace_back(P(par, i));
            }
        }
    }

    cout << N << " " << M << endl;
    assert(edges.size() == M);
    for (auto p : edges) {
        cout << p.first << " " << p.second << endl;
    }
}

yukicoder

結果

テストケース

ソースコード