結果

問題 No.488 四角関係
ユーザー Yut176
提出日時 2017-02-24 23:09:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,447 bytes
コンパイル時間 1,048 ms
コンパイル使用メモリ 95,644 KB
実行使用メモリ 13,648 KB
最終ジャッジ日時 2025-01-02 23:47:49
合計ジャッジ時間 37,530 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

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