CODE FESTIVAL 2016 qual A

Submission #1258727

Source codeソースコード

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

const int DIM = 2e5 + 5;

bitset<DIM> oki; long long val[DIM];
vector<pair<int, long long>> edg[DIM];

void dfs( int x, int r, bool &ok, long long &mn1, long long &mn2 ) {
    oki[x] = true;
    
    if( x <= r )
        mn1 = min( mn1, val[x] );
    else
        mn2 = min( mn2, val[x] );
    
    for( pair<int, long long> y : edg[x] ) {
        if( oki[y.first] == true )
            ok &= ( val[x] + val[y.first] == y.second );
        else {
            val[y.first] = y.second - val[x];
            dfs( y.first, r, ok, mn1, mn2 );
        }
    }
    
    return;
}

int main( void ) {
    
    int r, c, n;
    cin >> r >> c >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        int x, y, z;
        cin >> x >> y >> z;
        
        edg[x].push_back( make_pair( r + y, z ) );
        edg[r + y].push_back( make_pair( x, z ) );
    }
    
    bool ok = true;
    for( int i = 1; i <= r + c; i ++ ) {
        if( oki[i] == false ) {
            long long mn1 = numeric_limits<long long> :: max();
            long long mn2 = numeric_limits<long long> :: max();
           
            dfs( i, r, ok, mn1, mn2 );
            ok &= ( mn1 + mn2 >= 0 );
        }
    }
    
    
    cout << ( ( ok == true ) ? "Yes" : "No" ) << endl;
    return 0;
}

Submission

Task問題 D - マス目と整数 / Grid and Integers
User nameユーザ名 EmanuelNrx
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1360 Byte
File nameファイル名
Exec time実行時間 185 ms
Memory usageメモリ使用量 19584 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 3 ms 6400 KB
0_01.txt AC 3 ms 6400 KB
0_02.txt AC 3 ms 6400 KB
0_03.txt AC 3 ms 6400 KB
0_04.txt AC 3 ms 6400 KB
1_00.txt AC 5 ms 6400 KB
1_01.txt AC 5 ms 6400 KB
1_02.txt AC 5 ms 6400 KB
1_03.txt AC 5 ms 6400 KB
1_04.txt AC 5 ms 6400 KB
1_05.txt AC 5 ms 6400 KB
1_06.txt AC 118 ms 12800 KB
1_07.txt AC 149 ms 12800 KB
1_08.txt AC 114 ms 12032 KB
1_09.txt AC 112 ms 12032 KB
1_10.txt AC 157 ms 11776 KB
1_11.txt AC 161 ms 11776 KB
1_12.txt AC 165 ms 19584 KB
1_13.txt AC 174 ms 19584 KB
1_14.txt AC 165 ms 19584 KB
1_15.txt AC 161 ms 19584 KB
1_16.txt AC 123 ms 16640 KB
1_17.txt AC 138 ms 19200 KB
1_18.txt AC 136 ms 18304 KB
1_19.txt AC 142 ms 18432 KB
1_20.txt AC 93 ms 11008 KB
1_21.txt AC 43 ms 7936 KB
1_22.txt AC 9 ms 6656 KB
1_23.txt AC 91 ms 9728 KB
1_24.txt AC 115 ms 12160 KB
1_25.txt AC 91 ms 10624 KB
1_26.txt AC 11 ms 6656 KB
1_27.txt AC 19 ms 7040 KB
1_28.txt AC 148 ms 13184 KB
1_29.txt AC 49 ms 8192 KB
1_30.txt AC 137 ms 12288 KB
1_31.txt AC 57 ms 8448 KB
1_32.txt AC 117 ms 12288 KB
1_33.txt AC 137 ms 12160 KB
1_34.txt AC 20 ms 7040 KB
1_35.txt AC 122 ms 10752 KB
1_36.txt AC 23 ms 7168 KB
1_37.txt AC 57 ms 9344 KB
1_38.txt AC 106 ms 10112 KB
1_39.txt AC 34 ms 7680 KB
1_40.txt AC 105 ms 9984 KB
1_41.txt AC 50 ms 8320 KB
1_42.txt AC 124 ms 12544 KB
1_43.txt AC 93 ms 9728 KB
1_44.txt AC 120 ms 11520 KB
1_45.txt AC 37 ms 7808 KB
1_46.txt AC 135 ms 11904 KB
1_47.txt AC 47 ms 8320 KB
1_48.txt AC 44 ms 7936 KB
1_49.txt AC 16 ms 6912 KB
1_50.txt AC 78 ms 9600 KB
1_51.txt AC 185 ms 13312 KB
1_52.txt AC 13 ms 6784 KB
1_53.txt AC 25 ms 7168 KB
1_54.txt AC 45 ms 7936 KB
1_55.txt AC 57 ms 8704 KB
1_56.txt AC 97 ms 10368 KB
1_57.txt AC 144 ms 13824 KB
1_58.txt AC 122 ms 11520 KB
1_59.txt AC 10 ms 6656 KB
1_60.txt AC 3 ms 6400 KB
1_61.txt AC 3 ms 6400 KB
1_62.txt AC 3 ms 6400 KB
1_63.txt AC 3 ms 6400 KB