QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#894263#9525. Welcome to Join the Online Meeting!mutsumi114#WA 1ms3712kbC++232.6kb2025-02-11 14:33:282025-02-11 14:33:28

Judging History

This is the latest submission verdict.

  • [2025-02-11 14:33:28]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-02-11 14:33:28]
  • Submitted

answer

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

struct DSU {
    vector<int> fa;

    DSU(int n_) {
        init(n_);
    }

    void init(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
    }

    int getfa(int x) {
        if (x == fa[x]) {
            return x;
        }
        return fa[x] = getfa(fa[x]);
    }

    bool merge(int x, int y) {
        x = getfa(x);
        y = getfa(y);
        if (x == y) return false;
        fa[x] = y;
        return true;
    }

    bool same(int x, int y) {
        x = getfa(x);
        y = getfa(y);
        return x == y;
    }
};

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<bool> busy(n, false);
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        x--;
        busy[x] = true;
    }

    //vector<pair<int, int>> edge(m);
    vector<bool> del(n, false);
    DSU dsu(n);
    vector<vector<int>> invite(n);
    vector<vector<int>> e(n);

    int cp = n;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        //edge[i] = {x, y};
        if (busy[x] && busy[y]) continue;
        if (busy[x]) {
            if (!del[x]) {
                invite[y].push_back(x);
                cp--;
                del[x] = true;
            }
        } else if (busy[y]) {
            if (!del[y]) {
                invite[x].push_back(y);
                cp--;
                del[y] = true;
            }
        } else {
            e[x].push_back(y);
            e[y].push_back(x);
            if (dsu.merge(x, y)) {
                cp--;
            }
        }
    }
    
    if (cp != 1) {
        cout << "No\n";
        return;
    }

    vector<bool> vis(n, false);
    vector<int> ord;

    auto dfs = [&](this auto &&self, int x) -> void {
        vis[x] = true;
        
        ord.push_back(x);
        for (auto y: e[x]) {
            if (!vis[y] && !busy[y]) {
                self(y);
                invite[x].push_back(y);
            }
        }
    };

    for (int i = 0; i < n; i++) {
        if (!busy[i]) {
            dfs(i);
            break;
        }
    }

    cout << "Yes\n";
    cout << ord.size() << "\n";
    for (auto x: ord) {
        cout << x + 1 << " " << invite[x].size();
        for (auto y: invite[x]) {
            cout << " " << y + 1;
        }
        cout << "\n";
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    t = 1;
    while (t--) {
        solve();
    }
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

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

output:

Yes
2
1 3 3 4 2
2 0

result:

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