提出 #56576323

---

ソースコード 拡げる

/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#ifdef EMT
#include "Header/stdc++.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;

#ifdef EMT
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T, typename T2> ostream& operator<<(ostream &os, const pair<T, T2> &obj) {
    return os << '{' << obj.first << ',' << obj.second << '}';
}
template<class TupType, size_t... I> void lamy_kawaii(ostream& os, const TupType& _tup, index_sequence<I...>) {
    // source: https://stackoverflow.com/a/41171552
    os << '{';
    (..., (cerr << (I == 0? "" : ",") << get<I>(_tup)));
    os << '}';
}
template<class... T> ostream& operator<<(ostream &os, const tuple<T...>& _tup) {
    lamy_kawaii(os, _tup, make_index_sequence<sizeof...(T)>());
    return os;
}
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
    cerr << "\e[1;33m" << s << " = [";
    while (l != r) {
        cerr << *l;
        cerr << (++l == r ? ']' : ',');
    }
    cerr << "\e[0m\n";
}
#else
#define debug(x) 48763
#define print(x) 48763
#endif

template<typename T, typename T2> istream& operator>>(istream &is, pair<T, T2> &obj) {
    is >> obj.first >> obj.second;
    return is;
}
template<typename T> istream& operator>>(istream &is, vector<T> &obj) {
    for (auto &x : obj)
        is >> x;
    return is;
}

#define YN(x) ((x) ? "YES" : "NO")
#define Yn(x) ((x) ? "Yes" : "No")
#define yn(x) ((x) ? "yes" : "no")
#define emilia_my_wife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
template<typename T>
using base_type = remove_cv_t<remove_reference_t<T>>;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
    emilia_my_wife
    return 48763;
}();
/*--------------------------------------------------------------------------------------*/

// Returns n - rank
int gauss_elimination(vector<bitset<61>> &d) {
    int n = d.size(), m = d[0].size();
    int r = 0;
    for (int i = 0; i < m; ++i) {
        int p = -1;
        for (int j = r; j < n; ++j) {
            if (!d[j][i])
                continue;
            if (p == -1 || d[j][i] > d[p][i]) p = j;
        }
        if (p == -1) continue;
        swap(d[p], d[r]);
        for (int j = 0; j < n; ++j) {
            if (r == j) continue;
            int z = d[j][i];
            for (int k = 0; k < m; ++k) d[j][k] = d[j][k] ^ (z & d[r][k]);
        }
        r++;
    }
    return r;
}

signed main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> arr(n);
    for (int i = 0; i < m; i++) {
        int u, v;
         cin >> u >> v;
         u--; v--;
         arr[u].push_back(v);
         arr[v].push_back(u);
    }
    vector<ull> ans(n);
    for (int u = 0; u < n; u++) {
        vector<bitset<61>> matrix(n + 1);
        for (int i = 0; i < n; i++) {
            for (int v : arr[i]) {
                matrix[i][v] = true;
            }
        }
        matrix[n][u] = true;
        matrix[n][60] = true;
        int x = gauss_elimination(matrix);
        // debug(x);
        // for (int i = 0; i <= n; i++)
        //     cerr << matrix[i] << '\n';
        for (int i = 0; i < x; i++) {
            int w = 0;
            while (matrix[i][w] == 0)
                w++;
            if (w >= n) {
                cout << "No\n";
                return 0;
            }
            ans[w] |= ull(matrix[i][60]) << u;
        }
    }
    for (int i = 0; i < n; i++) {
        ull sum = 0;
        for (int v : arr[i])
            sum ^= ans[v];
        assert(sum == 0);
    }
    cout << "Yes\n";
    for (int i = 0; i < n; i++)
        cout << ans[i] << " \n"[i + 1 == n];
}

提出情報

ジャッジ結果