QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788457 | #9525. Welcome to Join the Online Meeting! | xixu | WA | 8ms | 49908kb | C++23 | 2.5kb | 2024-11-27 17:01:02 | 2024-11-27 17:01:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long
// #define int __int128
#define re read()
#define pr(x) print(x)
#define fup(a, b, c, d) for(int a = (b); a <= (c); a += (d))
#define fdo(a, b, c, d) for(int a = (b); a >= (c); a -= (d))
typedef long long ll;
typedef pair<int , int> PII;
typedef map<int , int> MII;
const int inf = 0x3f3f3f3f, N = 2e6 + 10, M = 4e5 + 10, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
set<int> se;
int in[N], p[N];
vector<vector<int>> E(N, vector<int> (0));
map<int , vector<int>> mp;
int find(int x) //返回x的祖宗结点+路径压缩优化
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void solve()
{
cin >> n >> m >> k;
fup(i, 1, n, 1) {
p[i] = i;
}
fup(i, 1, k, 1) {
int x;
cin >> x;
se.insert(x);
}
fup(i, 1, m, 1) {
int u, v;
cin >> u >> v;
if(u == v) continue ;
if(!se.count(u)) {
in[v] ++;
E[u].push_back(v);
}
if(!se.count(v)) {
in[u] ++;
E[v].push_back(u);
}
}
int cnt = 0, rt;
fup(i, 1, n, 1) {
if(se.count(i) && !in[i]) {
cout << "No\n";
return ;
}
if(!se.count(i)) rt = i;
if(!in[i]) {
if(cnt) {
cout << "No\n";
return ;
}
cnt = i;
}
}
if(!cnt) {
cnt = rt;
}
queue<int> q;
q.push(cnt);
int op = 0;
int nt = 0;
while(q.size()) {
auto t = q.front();
q.pop();
int pt = find(t);
vector<int> v;
for(auto x : E[t]) {
int px = find(x);
if(pt != px) {
if(nt > 1) break ;
p[px] = t;
v.push_back(px);
q.push(x);
}
}
if(v.size()) {
mp[t] = v;
op ++;
}
}
cout << "Yes\n";
cout << op << '\n';
for(auto x : mp) {
cout << x.first << ' ' << x.second.size() << ' ';
for(auto xx : x.second) {
cout << xx << ' ';
}
cout << '\n';
}
}
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
int _ = 1;
// cin >> _;
while(_ --)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 49908kb
input:
4 5 2 3 4 1 2 1 3 2 3 3 4 2 4
output:
Yes 1 2 3 1 3 4
result:
ok ok
Test #2:
score: 0
Accepted
time: 8ms
memory: 49748kb
input:
4 5 3 2 4 3 1 2 1 3 2 3 3 4 2 4
output:
No
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 49776kb
input:
4 6 2 3 4 1 3 1 4 2 3 2 4 1 2 3 4
output:
Yes 1 2 3 3 4 1
result:
ok ok
Test #4:
score: -100
Wrong Answer
time: 8ms
memory: 49788kb
input:
6 6 0 1 2 2 3 3 1 4 5 5 6 6 4
output:
Yes 1 6 2 5 4
result:
wrong answer member 1 is not invited