Submission #994875
Source Code Expand
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
vector.erase(vector.begin() + index);
}
int rootVal(int a, vector<int> &v){
if(v[a] < 0) return v[a] * -1;
return v[a] = rootVal(v[a], v);
}
int root(int a, vector<int> &v){
if(v[a] < 0) return a;
return v[a] = root(v[a], v);
}
bool connect(int a, int b, vector<int> &v, vector<int> &c1, vector<int> &c2, vector<bool> &ch, int &ind, vector<int> &lanlon, vector<int> &yet, int &l){
a = root(a, v);
b = root(b, v);
if(a == b) return false;
bool flag = false;
for(int i = 0; i < lanlon[a]; i++){
for(int j = 0; j < lanlon[b]; j++){
if(c1[i] == c2[j]){
flag = true;
break;
}
}
if(flag) break;
}
if(!flag) return false;
remove(yet, l);
l -= 1;
for(int i = 0; i < lanlon[b]; i++){
if(c2[i] == 0) break;
if(!ch[c2[i] - 1]){
ch[c2[i] - 1] = true;
c1[ind] = c2[i];
ind += 1;
lanlon[a] += 1;
}
}
if(v[a] > v[b]){
v[a] ^= v[b];
v[b] ^= v[a];
v[a] ^= v[b];
}
v[a] += v[b];
v[b] = a;
return true;
}
int main() {
int n, m;
int ind;
cin >> n >> m;
vector<int> uf(n);
vector<bool> ch(m);
vector<int> lanlon(n);
vector<int> yet;
for(int i = 0; i < n; i++){
uf[i] = -1;
}
vector<vector<int>>lang(n);
for(int i = 0; i < n; i++){
cin >> lanlon[i];
lang[i] = vector<int>(lanlon[i]);
if(i == 0){
ind = lanlon[i];
lang[i] = vector<int>(m);
}else{
yet.push_back(i);
}
for(int j = 0; j < lanlon[i]; j++){
cin >> lang[i][j];
}
}
for(int i = 0; i < m; i++){
if(lang[0][i] == 0) break;
ch[lang[0][i] - 1] = true;
}
while(1){
bool flag = false;
for(int i = 0; i < yet.size(); i++){
flag = connect(0, yet[i], uf, lang[0], lang[i], ch, ind, lanlon, yet, i);
}
if(!flag) break;
}
if(rootVal(0, uf) == n){
cout << "YES" << endl;
return 0;
}else{
cout << "NO" << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
toe42vbnys |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2095 Byte |
Status |
WA |
Exec Time |
763 ms |
Memory |
7288 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
0 / 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 |
2 ms |
256 KB |
01-02.txt |
AC |
3 ms |
256 KB |
01-03.txt |
WA |
3 ms |
256 KB |
01-04.txt |
AC |
3 ms |
256 KB |
01-05.txt |
WA |
3 ms |
256 KB |
01-06.txt |
AC |
3 ms |
256 KB |
01-07.txt |
AC |
3 ms |
256 KB |
01-08.txt |
WA |
3 ms |
256 KB |
01-09.txt |
AC |
3 ms |
256 KB |
01-10.txt |
AC |
3 ms |
256 KB |
02-01.txt |
AC |
34 ms |
1280 KB |
02-02.txt |
WA |
713 ms |
6648 KB |
02-03.txt |
WA |
40 ms |
1280 KB |
02-04.txt |
AC |
263 ms |
4348 KB |
02-05.txt |
AC |
496 ms |
5752 KB |
02-06.txt |
WA |
262 ms |
4348 KB |
02-07.txt |
AC |
620 ms |
6264 KB |
02-08.txt |
WA |
750 ms |
6904 KB |
02-09.txt |
AC |
763 ms |
7288 KB |
02-10.txt |
AC |
214 ms |
3964 KB |
02-11.txt |
WA |
215 ms |
3964 KB |
02-12.txt |
AC |
213 ms |
3964 KB |
02-13.txt |
WA |
214 ms |
3968 KB |
sample-01.txt |
AC |
3 ms |
256 KB |
sample-02.txt |
WA |
3 ms |
256 KB |