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
Submission Time |
|
Task |
C - Interpretation |
User |
ten986 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
2107 Byte |
Status |
AC |
Exec Time |
71 ms |
Memory |
9336 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
200 / 200 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
256 KB |
01-02.txt |
AC |
3 ms |
256 KB |
01-03.txt |
AC |
3 ms |
384 KB |
01-04.txt |
AC |
3 ms |
256 KB |
01-05.txt |
AC |
3 ms |
256 KB |
01-06.txt |
AC |
3 ms |
256 KB |
01-07.txt |
AC |
3 ms |
256 KB |
01-08.txt |
AC |
3 ms |
256 KB |
01-09.txt |
AC |
3 ms |
256 KB |
01-10.txt |
AC |
3 ms |
512 KB |
02-01.txt |
AC |
52 ms |
6144 KB |
02-02.txt |
AC |
55 ms |
6656 KB |
02-03.txt |
AC |
49 ms |
4480 KB |
02-04.txt |
AC |
63 ms |
7040 KB |
02-05.txt |
AC |
59 ms |
6016 KB |
02-06.txt |
AC |
63 ms |
7040 KB |
02-07.txt |
AC |
60 ms |
6144 KB |
02-08.txt |
AC |
46 ms |
6520 KB |
02-09.txt |
AC |
71 ms |
9336 KB |
02-10.txt |
AC |
51 ms |
6904 KB |
02-11.txt |
AC |
52 ms |
6904 KB |
02-12.txt |
AC |
51 ms |
6144 KB |
02-13.txt |
AC |
51 ms |
6272 KB |
sample-01.txt |
AC |
2 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |