結果

問題 No.488 四角関係
ユーザー noynotenoynote
提出日時 2017-02-24 22:51:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,359 bytes
コンパイル時間 1,423 ms
コンパイル使用メモリ 147,688 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-30 23:36:44
合計ジャッジ時間 2,424 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
4,376 KB
testcase_01 AC 6 ms
4,376 KB
testcase_02 AC 7 ms
4,376 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 9 ms
4,380 KB
testcase_06 AC 17 ms
4,376 KB
testcase_07 AC 17 ms
4,380 KB
testcase_08 AC 18 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<algorithm>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const int INF = 2000000000;
using namespace std;

    template < class BidirectionalIterator >
bool next_combination ( BidirectionalIterator first1 ,
        BidirectionalIterator last1 ,
        BidirectionalIterator first2 ,
        BidirectionalIterator last2 ){
    if (( first1 == last1 ) || ( first2 == last2 )) {
        return false ;
    }
    BidirectionalIterator m1 = last1 ;
    BidirectionalIterator m2 = last2 ; --m2;
    while (--m1 != first1 && !(* m1 < *m2 )){
    }
    bool result = (m1 == first1 ) && !(* first1 < *m2 );
    if (! result ) {
            while ( first2 != m2 && !(* m1 < * first2 )) {
                ++ first2 ;
            }
        first1 = m1;
        std :: iter_swap (first1 , first2 );
        ++ first1 ;
        ++ first2 ;
    }
    if (( first1 != last1 ) && ( first2 != last2 )) {
        m1 = last1 ; m2 = first2 ;
        while (( m1 != first1 ) && (m2 != last2 )) {
            std :: iter_swap (--m1 , m2 );
            ++ m2;
        }
        std :: reverse (first1 , m1 );
        std :: reverse (first1 , last1 );
        std :: reverse (m2 , last2 );
        std :: reverse (first2 , last2 );
    }
    return ! result ;
}

template < class BidirectionalIterator > bool next_combination ( BidirectionalIterator first , BidirectionalIterator middle , BidirectionalIterator last )
{
return next_combination (first , middle , middle , last );
}

int main(){
    int n, m;
    int g[55][55] = {0};
    cin >> n >> m;
    rep(i,m){
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1;
    }
    if(n <= 3){
        cout << 0 << endl;
        return 0;
    }

    vector<int> v;
    int ans = 0;
    rep(i,n) v.emplace_back(i);
    do{
        int sg[4][4];
        int cnt = 0;
        rep(i,4){
            int c = 0;
            rep(j,4){
                if(g[v[i]][v[j]]) c++;
            }
            if(c == 2) cnt++;
        }
        if(cnt == 4) ans++;
    }while(next_combination(v.begin(), v.begin() + 4, v.end()));
    cout << ans << endl;
}
0