QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709057#9525. Welcome to Join the Online Meeting!szjWA 8ms35036kbC++112.3kb2024-11-04 11:05:472024-11-04 11:05:47

Judging History

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

  • [2024-11-04 11:05:47]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:35036kb
  • [2024-11-04 11:05:47]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const long double PI = acos(-1);
const ll mod = 1e9 + 7;
const int maxn = 1e6 + 7;
const ll P = 133331;

ll qgcd(ll a, ll b) {
    return b == 0 ? a : qgcd(b, a % b);
}

ll qpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int n, m, k, x;
set<int> s;
int q[maxn], p[maxn], b[maxn], c[maxn];
vector<int> v[maxn];
bool vis[maxn];
vector<vector<int>> vt;

int find(int x, int a[]) {
	if (a[x] != x) {
		a[x] = find(a[x], a);
	}
	return a[x];
}

void dfs(int cur) {
	vector<int> vv;
	vv.push_back(cur);
	vis[cur] = 1;
	if (s.find(cur) != s.end())
		return;
	for (auto i: v[cur]) {
		if (vis[i])
			continue;
		vv.push_back(i);
		dfs(i);
	}
	vt.push_back(vv);
}

void solve() {
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		cin >> x;
		s.insert(x);
	}
	for (int i = 1; i <= n; i++) {
		b[i] = i;
		c[i] = i;
	}
	for (int i = 1; i <= m; i++) {
		cin >> q[i] >> p[i];
		v[q[i]].push_back(p[i]);
		v[p[i]].push_back(q[i]);
		if (s.find(q[i]) == s.end() && s.find(p[i]) == s.end()) {
			b[q[i]] = find(p[i], b);
		}
		c[q[i]] = find(p[i], c);
	}
	int flag1 = 1;
	int flag2 = 1;
	int x1 = 0;
	int x2 = find(1, c);
	for (int i = 1; i <= n; i++) {
		if (s.find(i) == s.end()) {
			x1 = find(i, b);
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (s.find(i) == s.end() && x1 != find(i, b)) {
			flag1 = 0;
		}
		if (x2 != find(i, c)) {
			flag2 = 0;
		}
	}
	if (flag1 == 0 || flag2 == 0) {
		cout << "No\n";
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (s.find(i) == s.end()) {
			dfs(i);
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0) {
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";
	cout << vt.size() << '\n';
	for (int i = vt.size() - 1; i >= 0; i--) {
		cout << vt[i][0] << " " << vt[i].size() - 1 << " ";
		for (int j = 1; j < vt[i].size(); j++) {
			cout << vt[i][j] << " ";
		}
		cout << "\n";
	}
}

int main() {
    IOS;
    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: 4ms
memory: 34332kb

input:

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

output:

Yes
2
1 1 2 
2 2 3 4 

result:

ok ok

Test #2:

score: 0
Accepted
time: 5ms
memory: 35036kb

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

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]