QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#671473 | #7738. Equivalent Rewriting | nageing | WA | 0ms | 3832kb | C++20 | 1.8kb | 2024-10-24 12:43:53 | 2024-10-24 12:43:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void solve() {
int n, m;
cin >> n >> m;
DSU dsu(m);
vector<int> rt(n);
vector<int> vis(m);
for (int i = 0; i < n; i ++) {
int k;
cin >> k;
vector<int> a(k);
for (int j = 0; j < k; j ++) {
cin >> a[j];
a[j] --;
vis[a[j]] = 1;
if (j > 0) {
dsu.merge(a[0], a[j]);
}
}
rt[i] = a[0];
}
int ans = 0;
for (int i = 0; i < m; i ++) {
int p = dsu.find(i);
if (vis[p]) {
vis[p] = 0;
ans ++;
}
}
if (ans > 1) {
cout << "Yes\n";
vector<int> res(n);
for (int i = 0; i < n; i ++) {
res[i] = i + 1;
}
int root = dsu.find(rt[0]);
for (int i = 1; i < n; i ++) {
int p = dsu.find(rt[i]);
if (p != root) {
cout << res[i] << ' ';
for (int j = 0; j < n; j ++) {
if (j != i) cout << res[j] << ' ';
}
break;
}
}
cout << '\n';
} else {
cout << "No\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
cin >> t;
while (t --) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
3 3 6 3 3 1 5 2 5 3 2 2 6 2 3 3 1 3 2 2 3 1 1 3 2 2 1
output:
Yes 3 1 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3832kb
input:
1 10 5 2 2 4 4 1 3 4 2 1 2 3 2 1 4 4 5 2 4 3 3 2 5 4 3 5 4 2 3 1 3 2 5 1 4 2 3 5 1 4
output:
No
result:
wrong answer jury found an answer but participant did not (test case 1)