QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788481#9525. Welcome to Join the Online Meeting!xixuWA 120ms80600kbC++232.6kb2024-11-27 17:07:352024-11-27 17:07:41

Judging History

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

  • [2024-11-27 17:07:41]
  • 评测
  • 测评结果:WA
  • 用时:120ms
  • 内存:80600kb
  • [2024-11-27 17:07:35]
  • 提交

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));
unordered_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, siz = 1;
    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 ++;
            siz += v.size();
        }
    }
    if(siz < n) {
        cout << "No\n";
        return ;
    }
    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: 4ms
memory: 51880kb

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

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: 4ms
memory: 51736kb

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: 8ms
memory: 52428kb

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: 120ms
memory: 80600kb

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
186051 1 142330 
42967 1 186051 
107050 1 42967 
159920 1 107050 
187359 1 159920 
111774 1 187359 
4643 1 111774 
22162 1 4643 
119911 1 22162 
165259 1 119911 
80747 1 165259 
145111 1 80747 
99600 1 145111 
157336 1 99600 
31914 1 157336 
158722 1 31914 
154002 1 158722 
156794 1 15400...

result:

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