結果

問題 No.408 五輪ピック
コンテスト
ユーザー dnk
提出日時 2016-08-05 23:25:50
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 45 ms / 5,000 ms
コード長 1,282 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,409 ms
コンパイル使用メモリ 186,592 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2026-03-08 15:48:51
合計ジャッジ時間 3,071 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

const int N = (int) 5e4;
vector<int> graph[N];
vector<int> nices[N];
bool visited[N];
int depth[N], a[N], b[N];

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int m; cin >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
        a[i] = u; b[i] = v;
    }
    queue<int> q; visited[0] = true; q.push(0);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : graph[u]) if (!visited[v]) {
            visited[v] = true;
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }
    for (int i = 0; i < m; ++i) {
        if (depth[a[i]] == 1) nices[b[i]].push_back(a[i]);
        if (depth[b[i]] == 1) nices[a[i]].push_back(b[i]);
    }
    for (int i = 0; i < m; ++i) if (a[i] != 0 && b[i] != 0) {
        if (nices[a[i]].size() > 2 && nices[b[i]].size() > 2) {
            cout << "YES" << endl;
            return 0;
        }
        for (auto x : nices[a[i]]) if (x != b[i])
            for (auto y : nices[b[i]]) if (y != a[i] && x != y) {
                cout << "YES" << endl;
                return 0;
            }
    }
    cout << "NO" << endl;
    return 0;
}
0