QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#735520#9525. Welcome to Join the Online Meeting!Foedere0WA 135ms40840kbC++203.5kb2024-11-11 20:29:412024-11-11 20:29:41

Judging History

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

  • [2024-11-11 20:29:41]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:40840kb
  • [2024-11-11 20:29:41]
  • 提交

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[find(x)] < sz[find(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: 9652kb

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: 0ms
memory: 9652kb

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: 2ms
memory: 9772kb

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

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: 128ms
memory: 40068kb

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: 135ms
memory: 40028kb

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: 135ms
memory: 40092kb

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: 57ms
memory: 40840kb

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: 41ms
memory: 33936kb

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: 0
Accepted
time: 55ms
memory: 37956kb

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
130511 1 66864 
66864 199997 52512 104330 139434 92884 185580 184115 137395 43463 118395 111697 133237 112507 140264 10 151082 155779 107988 148839 40909 172685 189374 180054 49 41830 19259 186287 41932 21357 66485 95229 126195 72801 154651 48615 111519 156500 156919 60203 11260 164641 168543 ...

result:

ok ok

Test #11:

score: 0
Accepted
time: 66ms
memory: 38016kb

input:

199998 199997 0

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

output:

Yes
1
77056 199997 67665 130538 101337 73749 138128 1274 108069 50961 7039 109946 170551 193330 113590 92775 2146 43591 125033 75583 173991 46820 3986 163272 91657 92212 191670 170218 149297 164182 6856 61891 95065 7257 47282 126716 84031 52189 32847 63118 134126 143246 30142 58215 3315 175496 98119...

result:

ok ok

Test #12:

score: -100
Wrong Answer
time: 50ms
memory: 10124kb

input:

1000 499500 999
458 720 932 821 847 788 447 593 430 896 257 238 380 924 968 30 389 306 278 824 83 342 329 513 476 313 714 348 602 105 758 777 663 1000 20 756 546 256 123 340 69 244 772 625 390 557 911 272 496 127 409 436 845 574 958 921 24 17 770 630 851 147 178 976 77 181 230 723 974 345 501 683 24...

output:

Yes
1
0 18446744073709551615 

result:

wrong answer Integer parameter [name=x_j] equals to 0, violates the range [1, 1000]