結果
問題 |
No.1147 土偶Ⅱ
|
ユーザー |
![]() |
提出日時 | 2021-08-10 14:48:35 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 500 ms |
コード長 | 1,671 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 144,384 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 15:54:29 |
合計ジャッジ時間 | 2,312 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <limits.h> #include <map> #include <queue> #include <set> #include <string.h> #include <vector> using namespace std; typedef long long ll; const int MAX_N = 110; vector<int> E[MAX_N]; bool is_friend[MAX_N][MAX_N]; bool is_out[MAX_N][MAX_N]; struct Node { int u; int dist; Node(int u = -1, int dist = -1) { this->u = u; this->dist = dist; } }; int main() { memset(is_friend, false, sizeof(is_friend)); memset(is_out, false, sizeof(is_out)); int N, M; cin >> N >> M; int a, b; for (int i = 0; i < M; ++i) { cin >> a >> b; is_friend[a][b] = true; is_friend[b][a] = true; } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (not is_friend[i][j]) continue; E[i].push_back(j); } } for (int i = 1; i <= N; ++i) { queue<Node> que; que.push(Node(i, 0)); while (not que.empty()) { Node node = que.front(); que.pop(); if (node.dist == 2) { is_out[i][node.u] = true; is_out[node.u][i] = true; continue; } for (int v : E[node.u]) { if (node.dist == 1) { if (i == v) continue; if (is_friend[i][v]) continue; } que.push(Node(v, node.dist + 1)); } } } int ans = 0; for (int i = 1; i <= N; ++i) { for (int j = i + 1; j <= N; ++j) { if (is_out[i][j]) continue; for (int k = j + 1; k <= N; ++k) { if (is_out[i][k]) continue; if (is_out[j][k]) continue; ++ans; } } } cout << ans << endl; return 0; }