QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685131 | #9528. New Energy Vehicle | ucup-team5077# | WA | 0ms | 22160kb | C++17 | 2.2kb | 2024-10-28 17:50:44 | 2024-10-28 17:50:44 |
Judging History
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'