QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #592060 | #7080. Chiaki Chain | Afterlife# | WA | 1ms | 5628kb | C++20 | 6.1kb | 2024-09-26 20:25:12 | 2024-09-26 20:25:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ull=unsigned long long;
const int N=2e5+1e3+7;
int n,m,k,T;
vector<int> g[N],e[N];
int dfn[N],dc,fa[N];
mt19937_64 rng(58);
vector<pii> ext;
ull dv[N];
void dfs(int x,int f)
{
dfn[x]=++dc;
fa[x]=f;
for(auto v:g[x])
{
if(v==f)
continue;
if(!dfn[v])
dfs(v,x),e[x].push_back(v);
else if(dfn[v]<dfn[x])
ext.push_back({x,v});
}
}
void getv(int x)
{
for(auto v:e[x])
{
getv(v);
dv[x]^=dv[v];
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
g[i].clear(),e[i].clear(),dv[i]=0;
set<pair<int,int> >es;
int sc=0;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
es.insert({min(u,v),max(u,v)});
sc|=u==v;
g[u].push_back(v);
g[v].push_back(u);
}
int d4=0;
for(int i=1;i<=n;i++)
{
if(g[i].size()>3)
d4=1;
}
if(d4)
{
cout<<"No\n";
continue;
}
if(es.size()!=m||sc)
{
cout<<"No\n";
continue;
}
fill(dfn,dfn+n+1,0);
dc=0;
ext.clear();
dfs(1,0);
if(dc!=n)
{
cout<<"No\n";
continue;
}
vector<ull> val;
map<ull,vector<pii> >cir;
for(auto [u,v]:ext)
{
val.push_back(rng());
cir[val.back()].push_back({u,v});
dv[u]^=val.back();
dv[v]^=val.back();
}
getv(1);
int ok=1;
for(int i=2;i<=n;i++)
{
if(!dv[i])
continue;
if(!cir.count(dv[i]))
{
ok=0;
break;
}
cir[dv[i]].push_back({i,fa[i]});
}
if(!ok)
{
cout<<"No\n";
continue;
}
if(cir.size()!=k)
{
cout<<"No\n";
continue;
}
{
multiset<int> csize;
for(auto &[x,v]:cir)
csize.insert(v.size());
int csz=1;
for(int i=3;i<=k+2;i++)
if(csize.count(i)!=1)
csz=0;
if(!csz)
{
cout<<"No\n";
continue;
}
}
vector<ull> onc(n+1);
for(auto [val,v]:cir)
for(auto [x,y]:v)
onc[x]=onc[y]=val;
vector<vector<vector<int> > >pt(n+1);
for(auto [val,v]:cir)
{
set<int> s3;
for(auto [x,y]:v)
{
if(g[x].size()==3)
s3.insert(x);
if(g[y].size()==3)
s3.insert(y);
}
if(s3.size()!=1)
{
ok=0;
break;
}
auto u=*s3.begin();
int d=0,la=-1;
int f3=-1;
vector<int> path;
int ou=u;
while(1)
{
path.push_back(u);
vector<int> tar;
for(auto v:g[u])
{
if(v==la||onc[v]==onc[ou])
continue;
tar.push_back(v);
}
if(!tar.size())
break;
la=u;
u=tar[0];
if(g[u].size()==3)
{
f3=u;
break;
}
}
if(f3==-1)
ok&=(k==1&&path.size()>2);
else
{
if(onc[f3])
ok&=(k==2&&path.size()>=3);
else
{
pt[f3].push_back(path);
}
}
}
int c2=0;
vector<int> tag(n+1);
for(int i=1;i<=n;i++)
if(val[i])
tag[i]=1;
for(int i=1;i<=n;i++)
{
if(pt[i].size()==0)
continue;
else if(pt[i].size()==1)
{
for(auto x:pt[i][0])
tag[x]=1;
}
else if(pt[i].size()==2)
{
c2++;
int fd=0;
for(auto v:pt[i])
{
if(v.size()==1)
tag[v[0]]=1;
else
{
if(!fd)
{
fd=1;
tag[v[0]]=1;
}
else
{
for(auto x:v)
tag[x]=1;
}
}
}
if(!fd)
ok=0;
}
else
ok=0;
}
ok&=c2<=2;
if(!ok)
{
cout<<"No\n";
continue;
}
map<int,int> deg;
for(int i=1;i<=n;i++)
for(auto j:g[i])
{
if(j<i)
continue;
if(tag[i]||tag[j])
continue;
deg[i]++,deg[j]++;
}
vector<int> cd(2);
for(auto [x,d]:deg)
{
if(d>2)
{
ok=0;
break;
}
cd[d-1]++;
}
if(cd[0]!=2&&cd[0]!=0)
ok=0;
if(!ok)
{
cout<<"No\n";
continue;
}
cout<<"Yes\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5616kb
input:
2 20 22 3 1 2 2 3 3 4 4 5 5 6 2 7 7 8 8 9 9 10 10 11 11 12 12 8 3 13 13 14 14 15 15 16 16 13 5 17 17 18 18 19 19 20 20 18 5 6 3 1 2 2 3 3 4 4 5 5 1 1 3
output:
Yes No
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5628kb
input:
31 20 22 3 1 2 2 3 3 4 4 5 5 6 2 7 7 8 8 9 9 10 10 11 11 12 12 8 3 13 13 14 14 15 15 16 16 13 5 17 17 18 18 19 19 20 20 18 5 6 3 1 2 2 3 3 4 4 5 5 1 1 3 20 22 3 1 2 2 3 3 4 4 5 5 6 2 7 7 8 8 9 9 10 10 11 11 12 12 8 3 13 13 14 14 15 15 16 16 13 2 17 17 18 18 19 19 20 20 18 20 22 3 1 2 2 3 3 4 4 5 5 6...
output:
Yes No No No No Yes Yes Yes Yes No No No No No No No No No No No No No Yes No No No No No No No No
result:
wrong answer 5th words differ - expected: 'Yes', found: 'No'