QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735419#9525. Welcome to Join the Online Meeting!Foedere0WA 163ms42592kbC++203.1kb2024-11-11 19:51:152024-11-11 19:51:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 19:51:15]
  • 评测
  • 测评结果:WA
  • 用时:163ms
  • 内存:42592kb
  • [2024-11-11 19:51:15]
  • 提交

answer

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int p[N];
int a[N];
unordered_map<int, int> st;
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
vector<int> ans[N];
vector<int> res;
vector<int> r;
unordered_map<int, int> mp;
unordered_map<int, int> w;
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= k; i++)
    {
        cin >> a[i];
        st[a[i]] = 1;
    }
    vector<PII> op;
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        if (st[x] == 1 && !st[y])
        {
            st[x] = 2;
            ans[y].push_back(x);
            if (!mp[y])
            {
                mp[y] = 1;
                r.push_back(y);
            }
        }
        if (st[y] == 1 && !st[x])
        {
            st[y] = 2;
            ans[x].push_back(y);
            if (!mp[x])
            {
                mp[x] = 1;
                r.push_back(x);
            }
        }
        if (!st[y] && !st[x])
        {
            op.push_back({x, y});
        }
    }
    int x = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            x = i;
            break;
        }
    }
    if (x == 0)
    {
        cout << "No" << endl;
        return;
    }
    int cnt = 0;
    // sort(op.begin(), op.end());
    for (auto [x, y] : op)
    {
        if (find(x) > find(y))
            swap(x, y);
        if (find(y) != find(x))
        {
            if (!st[x])
            {
                st[x] = 1;
                res.push_back(x);
            }
            ans[x].push_back(y);
            ans[y].push_back(x);
            p[find(y)] = find(x);
            cnt++;
        }
        if (cnt == n - k - 1)
            break;
    }
    if (cnt < n - k - 1)
    {
        cout << "No" << endl;
        return;
    }
    for (int i = 1; i <= k; i++)
    {
        if (st[a[i]] != 2)
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
    for (auto x : r)
    {
        if (!st[x])
        {
            st[x] = 1;
            res.push_back(x);
        }
    }
    cout << res.size() << endl;
    queue<int> heap;
    heap.push(res[0]);
    while (!heap.empty())
    {
        int o = heap.front();
        w[o] = 1;
        heap.pop();
        // cout << ans[o].size() << " ";
        vector<int> q;
        for (auto p : ans[o])
        {
            if (w[p])
                continue;
            q.push_back(p);
        }
        if (q.size() == 0)
            continue;
        cout << o << " ";
        cout << q.size() << " ";
        for (auto p : q)
        {
            cout << p << " ";
            if (ans[p].size() > 0)
                heap.push(p);
        }
        cout << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7720kb

input:

4 5 2
3 4
1 2
1 3
2 3
3 4
2 4

output:

Yes
2
1 2 3 2 
2 1 4 

result:

ok ok

Test #2:

score: 0
Accepted
time: 2ms
memory: 7616kb

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: 3ms
memory: 7672kb

input:

4 6 2
3 4
1 3
1 4
2 3
2 4
1 2
3 4

output:

Yes
1
1 3 3 4 2 

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 7672kb

input:

6 6 0

1 2
2 3
3 1
4 5
5 6
6 4

output:

No

result:

ok ok

Test #5:

score: -100
Wrong Answer
time: 163ms
memory: 42592kb

input:

200000 199999 2
142330 49798
49798 116486
116486 64386
64386 192793
192793 61212
61212 138489
138489 83788
83788 89573
89573 8596
8596 156548
156548 41800
41800 14478
14478 27908
27908 82806
82806 9353
9353 160166
160166 92308
92308 36265
36265 126943
126943 190578
190578 191148
191148 177381
177381...

output:

Yes
199988
64386 2 116486 192793 
116486 1 49798 
192793 1 61212 
61212 1 138489 
138489 1 83788 
83788 1 89573 
89573 1 8596 
8596 1 156548 
156548 1 41800 
41800 1 14478 
14478 1 27908 
27908 1 82806 
82806 1 9353 
9353 1 160166 
160166 1 92308 
92308 1 36265 
36265 1 126943 
126943 1 190578 
1905...

result:

wrong answer member 4643 is not invited