QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685131#9528. New Energy Vehicleucup-team5077#WA 0ms22160kbC++172.2kb2024-10-28 17:50:442024-10-28 17:50:44

Judging History

This is the latest submission verdict.

  • [2024-10-28 17:50:44]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 22160kb
  • [2024-10-28 17:50:44]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mapa make_pair
typedef long double ld;
typedef unsigned long long ull;
template <typename T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c<'0'||c>'9';c=getchar()) f|=(c=='-');
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+(c^48);
	x=(f?-x:x);
}
#define ep emplace_back
const int N=2e5+5;
int n, m, K;
int tag[N];
unordered_map<int, bool> e[N];
int que[N], hh, tt;
vector<int> vec[N];
vector<int> beg;
inline int calc(int x){
	if(vec[x].empty()) return 0;
	int ret=1;
	for(auto t:vec[x]) ret+=calc(t);
	return ret;
}
inline void work(int x){
	if(vec[x].empty()) return ;
	printf("%d %d ", x, (int)vec[x].size());
	for(auto t:vec[x]) printf("%d ", t);
	putchar('\n');
	for(auto t:vec[x]) work(t);
}
bool vis[N];
int fa[N];
inline int get(int x){
	while(x!=fa[x]){
		x=fa[x]=fa[fa[x]];
	}
	return x;
}
inline void merge(int x, int y){
	x=get(x); y=get(y);
	fa[x]=y;
}
int sum[N];
int main(){
	// freopen("D:\\nya\\test.in","r",stdin);
	// freopen("D:\\nya\\test.out","w",stdout);
	read(n); read(m); read(K);
	for(int i=1; i<=n; ++i) fa[i]=i;
	for(int i=1, x; i<=K; ++i) read(x), tag[x]=1, que[i]=x, vis[x]=1;
	hh=1; tt=K;
	for(int i=1, x, y; i<=m; ++i){
		read(x); read(y);
		e[x][y]=e[y][x]=1;
		merge(x, y);
	}
	for(int i=1; i<=n; ++i) sum[get(i)]+=tag[i];
	bool flg=0;
	for(int i=1; i<=n; ++i) if(i==get(i)&&sum[i]==0) {
		if(flg) {
			printf("No\n");
			return 0;
		}
		flg=1;
		bool flg2=0;
		for(int j=1; j<=n; ++j) if(get(j)==i&&e[j].size()==1){
			flg2=1;
			que[++tt]=j; break;
		}
		if(!flg2) que[++tt]=i;
	}
	while(hh<=tt){
		int x=que[hh++];
		bool suc=1;
		for(auto t:e[x]){
			if(!tag[t.fi]&&suc) {
				suc=0;
				vec[t.fi].ep(x);
			}
			e[t.fi].erase(e[t.fi].find(x));
			if(!vis[t.fi]) que[++tt]=t.fi, vis[t.fi]=1;
		}
		if(suc){
			if(tag[x]){
				printf("No\n");
				return 0;
			}
			beg.ep(x);
		}
	}
	if(beg.size()>1) {
		printf("No\n");
		return 0;
	}
	printf("Yes\n");
	printf("%d\n", calc(beg[0]));
	work(beg[0]);
	return 0;
}

詳細信息

Test #1:

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

input:

2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1

output:

No

result:

wrong answer 1st lines differ - expected: '12', found: 'No'