QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764866 | #7738. Equivalent Rewriting | mobbb | WA | 1ms | 3780kb | C++20 | 1.9kb | 2024-11-20 10:58:33 | 2024-11-20 10:58:38 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
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;
std::cin >> n >> m;
std::vector<std::vector<int>> b(n);
std::vector<int> lst(m, -1);
DSU d(m);
for (int i = 0; i < n; i++){
int p;
std::cin >> p;
b[i].resize(p);
for (int j = 0; j < p; j++){
std::cin >> b[i][j];
b[i][j]--;
lst[b[i][j]] = i;
if (j){
d.merge(b[i][j], b[i][j - 1]);
}
}
}
std::set<int> q;
for (int i = 0; i < m; i++){
if (lst[d.find(i)] != -1){
q.insert(lst[d.find(i)]);
}
}
if (q.size() < 2){
std::cout << "No\n";
return;
}
std::cout << "Yes\n";
std::vector<int> ans(n);
std::iota(ans.begin(), ans.end(), 0);
std::swap(ans[*q.begin()], ans[*(std::next(q.begin()))]);
for (int i = 0; i < n; i++){
std::cout << ans[i] + 1 << " \n"[i == n - 1];
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3780kb
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: -100
Wrong Answer
time: 1ms
memory: 3560kb
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)