QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#713734#9525. Welcome to Join the Online Meeting!ProaesWA 0ms3624kbC++203.2kb2024-11-05 20:25:112024-11-05 20:25:11

Judging History

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

  • [2024-11-05 20:25:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3624kb
  • [2024-11-05 20:25:11]
  • 提交

answer

/**
 *    title:  g.cpp
 *    author:  Proaes Meluam
 *    created:  2024-11-05 18:16:30
**/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h" 
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double pi = acos(-1);
const double E = exp(1);
constexpr ll mod = 1e9 + 7;
// constexpr int inf = 0x3f3f3f3f;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> s(k + 1);
    vector<int> mp(n + 1, 1);
    vector<int> vis(n + 1);
    vector<int> fa(n + 1);
    vector<vector<int>> adj1(n + 1, vector<int>(0));
    vector<vector<int>> adj2(n + 1, vector<int>(0));
    // vector<vector<int>> ans(n + 1, vector<int>(0));
    // vector<int> ans(0);
    vector<ll> dsu(n + 1); // dsu[i]存是 i 的祖宗结点(未必路径压缩好了,所以求祖宗结点需调用find函数)
    vector<ll> dsus(n + 1 , 1); // dsus[i]存 i 所在图的大小
    iota(dsu.begin() , dsu.end() , 0);
    auto find = [&](auto self , ll a) {
        if (a == dsu[a]) {
            return a;
        } else {
            dsu[a] = self(self , dsu[a]);
            return dsu[a];
        }
    };

    auto merge = [&] (ll a , ll b) {
        int x = find(find, a);
        int y = find(find, b);
        if (x != y) {
            if (dsus[x] < dsus[y]) {
                swap(x, y);
            }
            dsu[y] = x;
            dsus[x] += dsus[y];
        }
    };

    for (int i = 1; i <= k; ++ i) {
        cin >> s[i];
        mp[s[i]] = 0;
    }

    for (int i = 1; i <= m; ++ i) {
        int u, v;
        cin >> u >> v;
        merge(u, v);
        if (mp[u] == 1) adj1[u].emplace_back(v);
        if (mp[v] == 1) adj1[v].emplace_back(u);
    }
    int root = 0;
    for (int i = 1; i <= n; ++ i) {
        if (mp[i] == 1) {
            root = i;
            break;
        }
    }

    auto dfs1 = [&](auto self, int cur) -> void {
        for (auto child : adj1[cur]) {
            if (vis[child] == 1) continue;
            vis[child] = 1;
            self(self, child);
            adj2[cur].emplace_back(child);
        }
    };
    auto bfs = [&](int cur) {
        queue<int> q;
        q.push(cur);
        while (q.size() > 0) {
            int x = q.front();
            q.pop();
            int len = adj2[x].size();
            if (len > 0) {
                cout << x << " " << len << " ";
                for (auto child : adj2[x]) {
                    q.push(child);
                    cout << child << " ";
                }
                cout << "\n";
            }

        }
    };

    map<int, int>mpn;
    for (int i = 1; i <= n; ++ i) {
        dsu[i] = find(find, dsu[i]);
    }

    for (int i = 1; i <= n; ++ i) {
        mpn[dsu[i]] = 1;
    }

    if ((int)mpn.size() > 1) {
        cout << "No\n";
        return 0;
    }

    vis[root] = 1;
    dfs1(dfs1, root);
    int all = 0;
    for (int i = 1; i <= n; ++ i) {
        int len = adj2[i].size();
        all += len;
    }
    if (all + 1 == n) {
        cout << "Yes\n";
        // bfs(root);
    } else {
        cout << "No\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3624kb

input:

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

output:

Yes

result:

wrong output format Unexpected end of file - int32 expected