QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#754539 | #9531. Weird Ceiling | ANIG# | WA | 0ms | 18672kb | C++14 | 1.6kb | 2024-11-16 15:16:41 | 2024-11-16 15:16:43 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 2e5+5;
int n, fa[N], mk[N], k, m, vis[N];
vector <int> e[N], ne[N];
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void mer (int x, int y) {
x = find(x); y = find(y);
if (x^y) fa[x] = y;
}
void dfs (int p, int fa) {
vis[p] = 1;
for (int i : e[p]) {
if (vis[i]) continue;
ne[p].pb(i); ne[i].pb(p);
dfs(i, p);
}
}
vector <int> td, ch[N];
void dfs2 (int p, int fa) {
for (int i : ne[p]) {
if (i == fa) continue;
ch[p].pb(i); dfs2(i, p);
}
if (ch[p].size()) {
td.pb(p);
}
}
int main () {
cin >> n >> m >> k;
for (int i = 1;i <= k;i++) {
int x; cin >> x; mk[x] = 1;
}
for (int i = 1;i <= n;i++) fa[i] = i;
for (int i = 1;i <= m;i++) {
int x, y; cin >> x >> y;
e[x].pb(y); e[y].pb(x);
if (!mk[x] && !mk[y]) mer(x, y);
}
int fl = 0;
for (int i = 1;i <= n;i++) if (!mk[i]) fl = find(i);
if (!fl) {
puts("No"); return 0;
}
for (int i = 1;i <= n;i++) if (!mk[i] && find(i) != fl) {
puts("No"); return 0;
}
for (int i = 1;i <= n;i++) {
if (mk[i]) continue;
for (int j : e[i]) {
if (!mk[j] || vis[j]) continue;
vis[j] = 1; ne[i].pb(j); ne[j].pb(i);
}
}
dfs(fl, 0);
dfs2(fl, 0);
puts("Yes");
cout << td.size() << "\n";
for (int I = td.size()-1; ~I; I--) {
int i = td[I];
cout << i << " " << ch[i].size() << " ";
for (int j : ch[i]) cout << j << " "; cout << "\n";
}
return 0;
}
/*
4 5 3
3 2 4
1 2
1 3
2 3
3 4
2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18672kb
input:
3 5 451 114514
output:
No
result:
wrong answer 1st lines differ - expected: '21', found: 'No'