結果
問題 | No.488 四角関係 |
ユーザー |
|
提出日時 | 2017-02-25 00:38:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 5,000 ms |
コード長 | 2,961 bytes |
コンパイル時間 | 2,148 ms |
コンパイル使用メモリ | 170,628 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-03 02:18:41 |
合計ジャッジ時間 | 3,348 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#include "bits/stdc++.h"#include <random>using namespace std;#define rep(i,n) for(int i=0;i<(n);++i)#define rep2(i,a,b) for(int i=(a);i<(b);++i)#define rrep(i,n) for(int i=(n)-1;i>=0;--i)#define rrep2(i,a,b) for(int i=(a)-1;i>=b;--i)#define range(i,a,b,c) for(int i=a;\c>0?i<b:\i>b;\i+=c)#define chmax(a, b) (a = (a) < (b) ? (b) : (a))#define chmin(a, b) (a = (a) > (b) ? (b) : (a))using ll = long long;using ull = unsigned long long;using ld = long double;#define all(a) begin(a),end(a)#define ifnot(a) if(not (a))#define dump(x) cerr << #x << " = " << (x) << endl#define int long long#ifdef _MSC_VERconst bool test = true;#elseconst bool test = false;#endifint dx[] = { 1,0,-1,0 };int dy[] = { 0,1,0,-1 };const int INF = 1 << 28;const ll INFL = (ll)1 << 58;ll mod = (int)1e9 + 7;const double eps = 1e-10;typedef long double Real;// return -1, 0, 1int sgn(const Real& r) { return (r > eps) - (r < -eps); }int sgn(const Real& a, const Real &b) { return sgn(a - b); }//.....................const int MAX = (int)2e5 + 5;vector<string> split(const string &str, char sep) {vector<string> v;stringstream ss(str);string buffer;while (getline(ss, buffer, sep)) {v.push_back(buffer);}return v;}template<class InputIterator>int sum(InputIterator begin, InputIterator end) {return accumulate(begin, end, 0ll);}int H = 50;int W = 50;bool ng(int y, int x) {return y < 0 || H <= y || x < 0 || W <= x;}int N, M;vector<int> connect_[100];bool connect_matrix[100][100];bool visited[100];vector<int> visited_v;int dfs(int start, int pre, int now, int depth) {if (depth == 3) {if (visited_v.size() != 4) abort();auto tmp_vec = visited_v;if (not connect_matrix[start][now]) return 0;rep(i, 2) {if (connect_matrix[visited_v[i]][visited_v[i + 2]]) {return 0;}}if (test) {rep(i, 4) {cout << visited_v[i] << " ";}cout << endl;}return 1;}int res = 0;rep(i, connect_[now].size()) {int next = connect_[now][i];if (visited[next]) continue;visited[next] = true;visited_v.push_back(next);res += dfs(start, now, next, depth + 1);visited_v.pop_back();visited[next] = false;}return res;}void solve() {cin >> N >> M;rep(i, M) {int a, b;cin >> a >> b;connect_matrix[a][b] = true;connect_matrix[b][a] = true;connect_[a].push_back(b);connect_[b].push_back(a);}int res = 0;rep(i, N) {visited[i] = true;visited_v.push_back(i);res += dfs(i, i, i, 0);visited_v.pop_back();visited[i] = false;}cout << res / 8 << endl;}signed main() {srand(time(NULL));int T = 100;cout << fixed << setprecision(15);rep(i, T) {char s[MAX];if (scanf("%s", s) == EOF) break;int n = strlen(s);for (int i = n - 1; i > -1; i--) {ungetc(s[i], stdin);}solve();}return 0;}