#680067 (C++17) No.1610 She Loves Me, She Loves Me Not, ...

提出ソース

結果

問題	No.1610 She Loves Me, She Loves Me Not, ...
ユーザー	kuhaku
提出日時	2021-07-21 21:29:52
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	18 ms / 2,000 ms
コード長	5,039 bytes
コンパイル時間	2,627 ms
コンパイル使用メモリ	207,392 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-17 16:10:20
合計ジャッジ時間	3,484 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	17 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	17 ms 5,376 KB
testcase_06	AC	18 ms 5,376 KB
testcase_07	AC	17 ms 5,376 KB
testcase_08	AC	18 ms 5,376 KB
testcase_09	AC	18 ms 5,376 KB
testcase_10	AC	18 ms 5,376 KB
testcase_11	AC	17 ms 5,376 KB
testcase_12	AC	17 ms 5,376 KB
testcase_13	AC	18 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	2 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	2 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	2 ms 5,376 KB
testcase_35	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define FORR(i, m, n) for(int i = (m)-1; i >= (n); --i)
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FOR(i, 1, n+1)
#define repr(i, n) FORR(i, n, 0)
#define repnr(i, n) FORR(i, n+1, 1)
#define all(s) (s).begin(), (s).end()
template <class T, class U>
bool chmax(T &a, const U b) { return a < b ? a = b, true : false; }
template <class T, class U>
bool chmin(T &a, const U b) { return b < a ? a = b, true : false; }
template <class T>
istream &operator>>(istream &is, vector<T> &v) { for (T &i : v) is>>i; return is; }
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (auto it=v.begin(); it!=v.end(); ++it) { os<<(it==v.begin()?"":" ")<<*it; } return os;
}
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) {
    if constexpr(sizeof...(tail)==0) cout<<head<<'\n'; else cout<<head<<' ',co(forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) {
    if constexpr(sizeof...(tail)==0) cerr<<head<<'\n'; else cerr<<head<<' ',ce(forward<Tail>(tail)...);
}
template<typename T, typename... Args>
auto make_vector(T x, int arg, Args ...args) {
    if constexpr(sizeof...(args)==0) return vector<T>(arg, x); else return vector(arg,make_vector<T>(x, args...));
}
void sonic() { ios::sync_with_stdio(false); cin.tie(nullptr); }
void setp(const int n) { cout << fixed << setprecision(n); }
constexpr int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr int MOD = 1000000007;
constexpr int MOD_N = 998244353;
constexpr double EPS = 1e-7;
const double PI = acos(-1);

template <class T>
struct Graph {
    struct edge {
        int from, to;
        T dist;

        bool operator<(const edge &rhs) const { return dist < rhs.dist; }
        bool operator>(const edge &rhs) const { return rhs < *this; }
    };
    vector<vector<edge>> edges;

    Graph(int v) : edges(v) {}

    const auto &operator[](int i) const { return edges[i]; }
    auto &operator[](int i) { return edges[i]; }
    const auto begin() const { return edges.begin(); }
    auto begin() { return edges.begin(); }
    const auto end() const { return edges.end(); }
    auto end() { return edges.end(); }
    auto size() const { return edges.size(); }
    void add_edge(int a, int b, T d = T(1)) {
        edges[a].emplace_back(edge{a, b, d});
    }
    void add_edges(int a, int b, T d = T(1)) {
        edges[a].emplace_back(edge{a, b, d});
        edges[b].emplace_back(edge{b, a, d});
    }
    void input_edge(int m, bool zero_based = false) {
        for (int i = 0; i < m; ++i) {
            int a, b;
            T d;
            cin >> a >> b >> d;
            if (zero_based)
                this->add_edge(a, b, d);
            else
                this->add_edge(a - 1, b - 1, d);
        }
    }
    void input_edges(int m, bool zero_based = false) {
        for (int i = 0; i < m; ++i) {
            int a, b;
            T d;
            cin >> a >> b >> d;
            if (zero_based)
                this->add_edges(a, b, d);
            else
                this->add_edges(a - 1, b - 1, d);
        }
    }
};

template <>
struct Graph<void> {
    vector<vector<int>> edges;

    Graph(int v) : edges(v) {}

    const auto &operator[](int i) const { return edges[i]; }
    auto &operator[](int i) { return edges[i]; }
    const auto begin() const { return edges.begin(); }
    auto begin() { return edges.begin(); }
    const auto end() const { return edges.end(); }
    auto end() { return edges.end(); }
    auto size() const { return edges.size(); }
    void add_edge(int a, int b) { edges[a].emplace_back(b); }
    void add_edges(int a, int b) {
        edges[a].emplace_back(b);
        edges[b].emplace_back(a);
    }
    void input_edge(int m, bool zero_based = false) {
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            if (zero_based)
                this->add_edge(a, b);
            else
                this->add_edge(a - 1, b - 1);
        }
    }
    void input_edges(int m, bool zero_based = false) {
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            if (zero_based)
                this->add_edges(a, b);
            else
                this->add_edges(a - 1, b - 1);
        }
    }
};

// clang-format on

int main(void) {
    int n, m;
    cin >> n >> m;
    Graph<void> g(n);
    g.input_edges(m);

    vector<int> ed(n);

    rep(i, n) ed[i] = g[i].size();

    queue<int> que;

    int cnt = 0;
    rep(i, n) {
        rep(j, n) {
            if (ed[j] == 1) {
                ++cnt;
                ed[j] = 0;
                for (auto idx : g[j]) {
                    --ed[idx];
                }
                break;
            }
        }
    }


    if (cnt & 1) {
        puts("Yes");
    } else {
        puts("No");
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード