Submission #992515
Source Code Expand
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<unordered_set<int>>lang_graph(M);
vector<int>speaker_num(M);
rep(i, N) {
int K,x;
cin >> K;
vector<int>lang_list(K);
rep(j, K)cin >> lang_list[j];
rep(j, K)lang_list[j]--;//0-origin
rep(j, K)speaker_num[lang_list[j]]++;
rep(j, K)REP(x, j + 1, K) {
//lang_list[j]とlang_list[x]を話せる人がいるので辺を引く
lang_graph[lang_list[j]].insert(lang_list[x]);
lang_graph[lang_list[x]].insert(lang_list[j]);
}
}
//通訳を2人以上挟んでもいいと解釈して解く
vector<int>searched(M);
stack<int>dfs;
rep(i, M)if (speaker_num[i]) { dfs.push(i); break; }
while (!dfs.empty()) {
auto x = dfs.top(); dfs.pop();
if (searched[x])continue;
searched[x] = 1;
for (auto y : lang_graph[x]) {
dfs.push(y);
}
}
rep(i, M)if (searched[i] == 0 && speaker_num[i]) {
cout << "NO" << endl;
return 0;
}
cout << "YES" << endl;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
eukaryo |
Language |
C++14 (GCC 5.4.1) |
Score |
200 |
Code Size |
2176 Byte |
Status |
TLE |
Exec Time |
2131 ms |
Memory |
526096 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
0 / 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 |
3 ms |
256 KB |
01-02.txt |
AC |
6 ms |
1152 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 |
384 KB |
01-07.txt |
AC |
3 ms |
384 KB |
01-08.txt |
AC |
3 ms |
384 KB |
01-09.txt |
AC |
3 ms |
384 KB |
01-10.txt |
AC |
3 ms |
384 KB |
02-01.txt |
AC |
1006 ms |
104464 KB |
02-02.txt |
AC |
19 ms |
640 KB |
02-03.txt |
AC |
427 ms |
52864 KB |
02-04.txt |
AC |
54 ms |
12800 KB |
02-05.txt |
AC |
29 ms |
3200 KB |
02-06.txt |
AC |
58 ms |
12800 KB |
02-07.txt |
AC |
24 ms |
2048 KB |
02-08.txt |
AC |
16 ms |
256 KB |
02-09.txt |
AC |
29 ms |
7296 KB |
02-10.txt |
TLE |
2131 ms |
526096 KB |
02-11.txt |
TLE |
2131 ms |
520324 KB |
02-12.txt |
TLE |
2120 ms |
309760 KB |
02-13.txt |
TLE |
2120 ms |
311424 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
AC |
3 ms |
256 KB |