QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#727510#9525. Welcome to Join the Online Meeting!pugong#WA 56ms27884kbC++202.3kb2024-11-09 13:18:402024-11-09 13:18:41

Judging History

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

  • [2024-11-09 13:18:41]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:27884kb
  • [2024-11-09 13:18:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 


void solve() {
    int n, m, k;cin >> n >> m >> k;
    vector<int>mp(n + 1, 0), ok(n + 1, 0);
    for (int i = 1;i <= k;i++) {
        int x;cin >> x;
        mp[x] = 1;
        ok[x] = 1;
    }
    int ans = 1;
    vector<vector<int>>g(n + 1);
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        if (mp[u] && !mp[v]) ok[u] = 0;
        if (mp[v] && !mp[u]) ok[v] = 0;
    }
    int p = 1;
    for (int i = 1;i <= n;i++) {
        if (ok[i]) ans = 0;
        if (!mp[i]) p = i;
    }
    //cout << p << "--\n";
    vector<int>st(n + 1, 0);
    vector<int>id(n + 1, -1);
    int cnt = 1;
    auto dfs = [&](auto self, int u)->void {
        id[cnt++] = u;
        for (auto i : g[u]) {
            if (st[i]) continue;
            st[i] = 1;
            if (!mp[i]) {
                self(self, i);
            }
        }
        };
    st[p] = 1;
    dfs(dfs, p);
    for (int i = 1;i <= n;i++) {
        if (!st[i]) {
            ans = 0;
            //cout << i << "+\n";
        }
    }
    vector<int>use(n + 1, 0);
    if (!ans) {
        cout << "No\n";
    }
    else {
        cout << "Yes\n";
        int y = 0;
        for (int i = 0;i <= cnt;i++) {
            //cout << id[i] << "+\n";
            if (id[i] == -1 || use[id[i]]) continue;
            //cout << id[i] << " " << op << " ";
            for (auto j : g[id[i]]) {
                if (!use[j]) //cout << j << " ";
                    use[j] = 1;
            }
            y++;
        }
        use.assign(n + 1, 0);
        cout << y << "\n";
        for (int i = 0;i <= cnt;i++) {
            //cout << id[i] << "+\n";
            if (id[i] == -1 || use[id[i]]) continue;
            int op = 0;
            for (auto j : g[id[i]]) {
                if (!use[j]) op++;
            }
            cout << id[i] << " " << op << " ";
            for (auto j : g[id[i]]) {
                if (!use[j]) cout << j << " ";
                use[j] = 1;
            }
            cout << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

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

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

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

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: 56ms
memory: 27884kb

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
99999
200000 2 70619 64617 
61733 1 186765 
130197 1 60967 
185321 1 175404 
36785 1 46281 
117056 1 196740 
106390 1 80009 
93912 1 182518 
156904 1 108072 
11885 1 29113 
150864 1 90423 
58868 1 191535 
58618 1 11370 
151769 1 108421 
188488 1 168908 
36651 1 162568 
34249 1 193230 
196813 1 1...

result:

wrong answer on step #2, member 61733 is not invited before inviting others