QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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";
}
}
Details
Tip: Click on the bar to expand more detailed information
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'