QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672280 | #7738. Equivalent Rewriting | nageing | WA | 1ms | 3616kb | C++20 | 1.7kb | 2024-10-24 16:16:48 | 2024-10-24 16:16:53 |
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<vector<int>> g(n);
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] --;
}
g[i] = a;
}
vector<int> vis(m);
int cnt = 0;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < g[i].size(); j ++) {
if (j > 0) {
dsu.merge(g[i][0], g[i][j]);
}
}
int p = dsu.find(g[i][0]);
if (!vis[p]) {
vis[p] = 1;
cnt ++;
}
if (cnt > 1) {
cout << "Yes\n";
for (int j = 0; j < i - 1; j ++) {
cout << j + 1 << ' ';
}
cout << i + 1 << ' ' << i << ' ';
for (int j = i + 1; j < n; j ++) {
cout << j + 1 << ' ';
}
cout << '\n';
return;
}
}
cout << "No\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int t = 1;
cin >> t;
while (t --) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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 1 3 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3616kb
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:
Yes 2 1 3 4 5 6 7 8 9 10
result:
ok OK. (1 test case)
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
1 20 5 5 4 1 2 5 3 2 5 3 3 5 1 2 5 4 5 1 3 2 3 4 2 5 5 3 1 5 4 2 5 5 1 2 3 4 1 3 4 5 1 2 3 4 4 1 3 5 2 5 2 4 2 3 5 1 3 2 4 5 5 2 3 4 1 5 4 5 2 4 3 1 2 2 4 3 4 4 5 3 1 5 4 1 5 3 2 3 5 1 3
output:
No
result:
wrong answer jury found an answer but participant did not (test case 1)