CODE FESTIVAL 2016 qual A

Submission #899631

Source codeソースコード

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;

using namespace std;

int R, C, N;
vector<ll> w;

struct E{
    int to, cost;
    E(int t, int c): to(t), cost(c) {};
};
vector<vector<E> > edge;
ll rmin, cmin;

bool dfs(int v) {
    if(v < R) rmin = min(rmin, w[v]);
    else cmin = min(cmin, w[v]);
    REP(i, edge[v].size()) {
        E e = edge[v][i];
        if(w[e.to] != -1) {
            if(w[v]+w[e.to]!=e.cost) return false;
        } else {
            w[e.to] = e.cost - w[v];
            if(!dfs(e.to)) return false;
        }
    }
    return true;
}

int main(void) {
    int tr, tc, ta;
    cin >> R >> C >> N;

    edge.resize(R+C);
    REP(i, N) {
        cin >> tr >> tc >> ta;
        tr--; tc--;
        edge[tr].push_back(E(R+tc, ta));
        edge[R+tc].push_back(E(tr, ta));
    }

    w.resize(R+C);
    w.assign(R+C, -1);

    REP(i, R+C) {
        if(w[i] != -1 || edge[i].size() == 0) continue;
        w[i] = 0;
        rmin = numeric_limits<ll>::max();
        cmin = numeric_limits<ll>::max();
        if(!dfs(i) || rmin+cmin < 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Submission

Task問題 D - マス目と整数 / Grid and Integers
User nameユーザ名 kivantium
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1322 Byte
File nameファイル名
Exec time実行時間 162 ms
Memory usageメモリ使用量 12800 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_00.txt,0_01.txt,0_02.txt,0_03.txt,0_04.txt
All 800 / 800 0_00.txt,0_01.txt,0_02.txt,0_03.txt,0_04.txt,1_00.txt,1_01.txt,1_02.txt,1_03.txt,1_04.txt,1_05.txt,1_06.txt,1_07.txt,1_08.txt,1_09.txt,1_10.txt,1_11.txt,1_12.txt,1_13.txt,1_14.txt,1_15.txt,1_16.txt,1_17.txt,1_18.txt,1_19.txt,1_20.txt,1_21.txt,1_22.txt,1_23.txt,1_24.txt,1_25.txt,1_26.txt,1_27.txt,1_28.txt,1_29.txt,1_30.txt,1_31.txt,1_32.txt,1_33.txt,1_34.txt,1_35.txt,1_36.txt,1_37.txt,1_38.txt,1_39.txt,1_40.txt,1_41.txt,1_42.txt,1_43.txt,1_44.txt,1_45.txt,1_46.txt,1_47.txt,1_48.txt,1_49.txt,1_50.txt,1_51.txt,1_52.txt,1_53.txt,1_54.txt,1_55.txt,1_56.txt,1_57.txt,1_58.txt,1_59.txt,1_60.txt,1_61.txt,1_62.txt,1_63.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_00.txt AC 2 ms 256 KB
0_01.txt AC 3 ms 256 KB
0_02.txt AC 3 ms 256 KB
0_03.txt AC 3 ms 256 KB
0_04.txt AC 3 ms 256 KB
1_00.txt AC 10 ms 6528 KB
1_01.txt AC 10 ms 6528 KB
1_02.txt AC 10 ms 6528 KB
1_03.txt AC 10 ms 6528 KB
1_04.txt AC 10 ms 6528 KB
1_05.txt AC 10 ms 6528 KB
1_06.txt AC 128 ms 12800 KB
1_07.txt AC 153 ms 12800 KB
1_08.txt AC 123 ms 10624 KB
1_09.txt AC 119 ms 10624 KB
1_10.txt AC 148 ms 9600 KB
1_11.txt AC 151 ms 9600 KB
1_12.txt AC 155 ms 12800 KB
1_13.txt AC 151 ms 12800 KB
1_14.txt AC 162 ms 12800 KB
1_15.txt AC 153 ms 12800 KB
1_16.txt AC 130 ms 11648 KB
1_17.txt AC 143 ms 12672 KB
1_18.txt AC 138 ms 12288 KB
1_19.txt AC 142 ms 12288 KB
1_20.txt AC 86 ms 4736 KB
1_21.txt AC 43 ms 4480 KB
1_22.txt AC 10 ms 2560 KB
1_23.txt AC 92 ms 7808 KB
1_24.txt AC 106 ms 5504 KB
1_25.txt AC 85 ms 5120 KB
1_26.txt AC 11 ms 1152 KB
1_27.txt AC 21 ms 4224 KB
1_28.txt AC 148 ms 8192 KB
1_29.txt AC 50 ms 4992 KB
1_30.txt AC 131 ms 8320 KB
1_31.txt AC 65 ms 7424 KB
1_32.txt AC 108 ms 4352 KB
1_33.txt AC 131 ms 8320 KB
1_34.txt AC 21 ms 3456 KB
1_35.txt AC 116 ms 3840 KB
1_36.txt AC 24 ms 3840 KB
1_37.txt AC 54 ms 3072 KB
1_38.txt AC 107 ms 8192 KB
1_39.txt AC 37 ms 5504 KB
1_40.txt AC 103 ms 7680 KB
1_41.txt AC 56 ms 7680 KB
1_42.txt AC 110 ms 4864 KB
1_43.txt AC 90 ms 7424 KB
1_44.txt AC 115 ms 6912 KB
1_45.txt AC 36 ms 3456 KB
1_46.txt AC 129 ms 8192 KB
1_47.txt AC 46 ms 4224 KB
1_48.txt AC 40 ms 2944 KB
1_49.txt AC 18 ms 3072 KB
1_50.txt AC 74 ms 5248 KB
1_51.txt AC 123 ms 6656 KB
1_52.txt AC 16 ms 5248 KB
1_53.txt AC 26 ms 5120 KB
1_54.txt AC 45 ms 4480 KB
1_55.txt AC 55 ms 3200 KB
1_56.txt AC 91 ms 6272 KB
1_57.txt AC 134 ms 6656 KB
1_58.txt AC 113 ms 7168 KB
1_59.txt AC 13 ms 3968 KB
1_60.txt AC 2 ms 256 KB
1_61.txt AC 3 ms 256 KB
1_62.txt AC 2 ms 256 KB
1_63.txt AC 3 ms 256 KB