QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788457#9525. Welcome to Join the Online Meeting!xixuWA 8ms49908kbC++232.5kb2024-11-27 17:01:022024-11-27 17:01:11

Judging History

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

  • [2024-11-27 17:01:11]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:49908kb
  • [2024-11-27 17:01:02]
  • 提交

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));
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;
    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 ++;
        }
    }
    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: 3ms
memory: 49908kb

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

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

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: -100
Wrong Answer
time: 8ms
memory: 49788kb

input:

6 6 0

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

output:

Yes
1
6 2 5 4 

result:

wrong answer member 1 is not invited