Official

B - Everyone is Friends Editorial by en_translator


We manage whether person \(i\) and person \(j\) participated in the same party with a two-dimensional array.

For each party, we search exhaustively the pair of participants and update the aforementioned array to answer the problem in a total of \(\mathrm{O}(N^3)\) time.

Two-dimensional arrays are explained in the editorial of the last ABC-B.

See also the sample code below.

Sample code (C++):

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> chk(n, vector<bool>(n, false));
    for(int i = 0; i < m; i++) {
        int k;
        cin >> k;
        vector<int> a(k);
        for(auto &v : a) cin >> v, --v;
        for(int j = 0; j < (int)a.size() - 1; j++) {
            for(int k = j + 1; k < (int)a.size(); k++) {
                chk[a[j]][a[k]] = true;
            }
        }
    }
    bool ans = 1;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            ans &= chk[i][j];
        }
    }
    cout << (ans ? "Yes" : "No") << endl;
}

posted:
last update: