QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735510#9525. Welcome to Join the Online Meeting!Foedere0WA 205ms41404kbC++203.5kb2024-11-11 20:27:152024-11-11 20:27:17

Judging History

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

  • [2024-11-11 20:27:17]
  • 评测
  • 测评结果:WA
  • 用时:205ms
  • 内存:41404kb
  • [2024-11-11 20:27: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], sz[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;
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        sz[i] = 1;
        ans[i].push_back(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());
    int t = 0;
    for (auto [x, y] : op)
    {
        if (sz[x] < sz[y])
        {
            swap(x, y);
        }
        if (find(y) != find(x))
        {
            t = find(x);
            if (!st[x])
            {
                st[x] = 1;
                res.push_back(x);
            }
            // for (auto t : ans[y])
            //{
            //     ans[x].push_back(t);
            // }
            ans[x].push_back(y);
            sz[find(x)] += sz[find(y)];
            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 << t << endl;
    queue<int> heap;
    heap.push(t);
    cnt = 0;
    while (!heap.empty())
    {
        cnt++;
        int o = heap.front();
        // cout << o << endl;
        heap.pop();
        for (auto p : ans[o])
        {
            if (p == o)
                continue;
            if (ans[p].size() > 1)
                heap.push(p);
        }
    }
    cout << cnt << endl;
    heap.push(t);
    while (!heap.empty())
    {
        cnt++;
        int o = heap.front();
        heap.pop();
        cout << o << " ";
        cout << ans[o].size() - 1 << " ";
        for (auto p : ans[o])
        {
            if (p == o)
                continue;
            cout << p << " ";
            if (ans[p].size() > 1)
                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: 3ms
memory: 9780kb

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: 9664kb

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: 9716kb

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

input:

6 6 0

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

output:

No

result:

ok ok

Test #5:

score: 0
Accepted
time: 195ms
memory: 41404kb

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
199998
116486 2 49798 64386 
64386 1 192793 
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 
19057...

result:

ok ok

Test #6:

score: 0
Accepted
time: 205ms
memory: 39988kb

input:

199999 199998 1
136702
159826 166341
166341 59559
59559 169672
169672 102084
102084 136269
136269 57057
57057 59116
59116 119963
119963 85663
85663 33942
33942 84604
84604 189395
189395 154906
154906 22175
22175 144902
144902 198523
198523 35993
35993 35690
35690 47504
47504 104458
104458 68253
6825...

output:

Yes
199998
159826 1 166341 
166341 1 59559 
59559 1 169672 
169672 1 102084 
102084 1 136269 
136269 1 57057 
57057 1 59116 
59116 1 119963 
119963 1 85663 
85663 1 33942 
33942 1 84604 
84604 1 189395 
189395 1 154906 
154906 1 22175 
22175 1 144902 
144902 1 198523 
198523 1 35993 
35993 1 35690 
...

result:

ok ok

Test #7:

score: 0
Accepted
time: 203ms
memory: 38224kb

input:

199998 199997 0

67665 130538
130538 101337
101337 73749
73749 138128
138128 1274
1274 108069
108069 50961
50961 7039
7039 109946
109946 170551
170551 193330
193330 113590
113590 92775
92775 2146
2146 43591
43591 125033
125033 75583
75583 173991
173991 46820
46820 3986
3986 163272
163272 91657
91657...

output:

Yes
199997
67665 1 130538 
130538 1 101337 
101337 1 73749 
73749 1 138128 
138128 1 1274 
1274 1 108069 
108069 1 50961 
50961 1 7039 
7039 1 109946 
109946 1 170551 
170551 1 193330 
193330 1 113590 
113590 1 92775 
92775 1 2146 
2146 1 43591 
43591 1 125033 
125033 1 75583 
75583 1 173991 
173991...

result:

ok ok

Test #8:

score: 0
Accepted
time: 81ms
memory: 40096kb

input:

199997 199996 1
158877
35837 79489
79489 72932
72932 14238
14238 73007
73007 66909
66909 49015
49015 129581
129581 138449
138449 94774
94774 189625
189625 23578
23578 31043
31043 146625
146625 161587
161587 136966
136966 184859
184859 27587
27587 155616
155616 72392
72392 195320
195320 75551
75551 1...

output:

No

result:

ok ok

Test #9:

score: 0
Accepted
time: 69ms
memory: 33892kb

input:

200000 199999 1
29111
29111 80079
29111 131587
29111 197066
29111 125194
29111 156736
50697 29111
29111 74382
113595 29111
29111 26046
29111 172868
178564 29111
174875 29111
93471 29111
88216 29111
29111 147893
29111 145746
29111 34038
146500 29111
67862 29111
29111 19222
29111 121535
29111 49102
29...

output:

No

result:

ok ok

Test #10:

score: -100
Wrong Answer
time: 83ms
memory: 37428kb

input:

199999 199998 2
52512 104330
130511 66864
139434 66864
92884 66864
66864 185580
184115 66864
137395 66864
66864 43463
118395 66864
111697 66864
66864 133237
66864 112507
66864 140264
66864 10
66864 151082
155779 66864
107988 66864
148839 66864
66864 40909
172685 66864
66864 189374
180054 66864
49 66...

output:

Yes
2
114634 1 66864 
66864 99988 52512 104330 185580 43463 133237 112507 140264 10 151082 40909 189374 41830 19259 41932 21357 126195 72801 154651 48615 111519 60203 164641 130264 100544 25652 104015 164921 92202 15224 59849 179007 7091 34145 94588 125430 192466 161444 23782 49473 193810 61020 1000...

result:

wrong answer member 1 is not invited