Submission #992754

---

Source Code Expand

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)





int main()
{
	int N, M;
	cin >> N >> M;
	//N ひとのかず

	//M　ことばの数
	vector<vector<int>> tate(N + 1, vector<int>());
	vector<vector<int>> yoko(M + 1, vector<int>());
	REP(i, N) {
		int a;
		cin >> a;
		REP(j, a) {
			int b;
			cin >> b;
			tate[i + 1].push_back(b);
			yoko[b].push_back(i + 1);
		}
	}
	//true なら tate
	queue<pair<bool, int>> q;
	pair<bool, int> nanka;
	nanka.first = true;
	nanka.second = 1;
	q.push(nanka);

	vector<bool> tateEnd(N + 1, false);
	int tateEndNum = 0;
	vector<bool> yokoEnd(M + 1, false);

	bool flag = false;
	while (q.size() >= 1) {
		pair<bool, int> gomi = q.front();
		q.pop();
		if (gomi.first == true && tateEnd[gomi.second] == false) {
			tateEnd[gomi.second] = true;
			tateEndNum++;
			REP(i, tate[gomi.second].size()) {
				pair<bool, int> hoge;
				hoge.first = false;
				hoge.second = tate[gomi.second][i];
				q.push(hoge);
			}
		}
		else
			if (gomi.first == false && yokoEnd[gomi.second] == false) {
				yokoEnd[gomi.second] = true;
				REP(i, yoko[gomi.second].size()) {
					pair<bool, int> hoge;
					hoge.first = true;
					hoge.second = yoko[gomi.second][i];
					q.push(hoge);
				}
			}
		if (tateEndNum == N) {
			flag = true;
			break;
		}
	}
	if (flag) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;

	}
}

Submission Info

Judge Result