QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #591951 | #7080. Chiaki Chain | Afterlife# | WA | 1ms | 5880kb | C++20 | 5.9kb | 2024-09-26 19:22:41 | 2024-09-26 19:22:42 |
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;
int 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<int,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<int> onc(n+1);
for(auto [val,v]:cir)
for(auto [x,y]:v)
onc[x]=onc[y]=1;
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;
while(1)
{
path.push_back(u);
vector<int> tar;
for(auto v:g[u])
{
if(onc[v]||v==la)
continue;
tar.push_back(v);
}
if(!tar.size())
break;
u=tar[0];
if(g[u].size()==3)
{
f3=u;
break;
}
}
if(f3==-1)
ok&=k==1;
else
{
if(onc[f3])
ok&=k==2;
else
{
pt[f3].push_back(path);
}
}
}
int c2=0;
auto tag=onc;
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)
ok=0;
if(!ok)
{
cout<<"No\n";
continue;
}
cout<<"Yes\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
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: 5880kb
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'