結果

問題 No.488 四角関係
ユーザー Yut176Yut176
提出日時 2017-02-24 23:09:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,447 bytes
コンパイル時間 1,267 ms
コンパイル使用メモリ 91,412 KB
実行使用メモリ 7,884 KB
最終ジャッジ日時 2023-08-30 23:45:22
合計ジャッジ時間 7,814 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
using namespace std;

long long int cnt = 0;


bool check(vector< pair<int, int > > node, vector<int> b){
  int cnt = 0;
  for(int i=0; i<node.size(); i++){
    if( b[0] == node[i].first && b[1] == node[i].second ) cnt++;
    if( b[0] == node[i].first && b[2] == node[i].second ) cnt++;
    if( b[0] == node[i].first && b[3] == node[i].second ) cnt++;
    if( b[1] == node[i].first && b[2] == node[i].second ) cnt++;
    if( b[1] == node[i].first && b[3] == node[i].second ) cnt++;
    if( b[2] == node[i].first && b[3] == node[i].second ) cnt++;
    if( b[0] == node[i].second && b[1] == node[i].first ) cnt++;
    if( b[0] == node[i].second && b[2] == node[i].first ) cnt++;
    if( b[0] == node[i].second && b[3] == node[i].first ) cnt++;
    if( b[1] == node[i].second && b[2] == node[i].first ) cnt++;
    if( b[1] == node[i].second && b[3] == node[i].first ) cnt++;
    if( b[2] == node[i].second && b[3] == node[i].first ) cnt++;
  }
  // cerr << cnt << endl;
  return ( cnt == 4 ? true : false);
}

int dfs(vector< pair<int, int > > node, vector<bool> v, int s, int pos, int depth, vector<int> b){

  if( depth == 4 && pos == s ){
    if( check(node, b) ){
      cnt++;
      // for(int i=0; i<4; i++) cerr << b[i];
      // cerr << endl;
    }
    return 0;
  }
  if( depth > 4 ) return 0;

  for(int i=0; i<node.size(); i++){
    if( node[i].first == pos && !v[ node[i].second ] ){
      v[ node[i].second ] = true;
      // string str2 = str + to_string(node[i].first);
      b[depth] = node[i].first;
      dfs(node, v, s, node[i].second, depth+1, b);
      v[ node[i].second ] = false;
    }
    if( node[i].second == pos && !v[ node[i].first ] ){
      v[ node[i].first ] = true;
      // string str3 = str + to_string(node[i].second);
      b[depth] = node[i].second;
      dfs(node, v, s, node[i].first, depth+1, b);
      v[ node[i].first ] = false;
    }
  }

  return 0;
}


int main(){

  int n, m;
  cin >> n >> m;
  vector< pair<int, int> > p(m);
  for(int i=0; i<m; i++) cin >> p[i].first >> p[i].second;

  vector<bool> v(n, false);
  vector<int> b(4, -1);
  for(int i=0; i<n; i++){
    dfs(p, v, i, i, 0, b);
    // cerr << "  " << i << " " << cnt << endl;
  }
  // dfs(p, v, 0, 0, 0, "");
  cout << cnt / 8 << endl;

  return 0;
}
0