QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #592152 | #7080. Chiaki Chain | Afterlife# | TL | 109ms | 35888kb | C++20 | 7.3kb | 2024-09-26 20:58:15 | 2024-09-26 20:58:15 |
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,c3=0;
vector<int> tag(n+1);
// for(int i=1;i<=n;i++)
// if(dv[i]) {
// tag[i]=1;
// // printf("cir %d\n",i);
// }
for(auto &[x,v] : cir) {
for(auto [a,b] : v) tag[a] = tag[b] = 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 if(pt[i].size()==3)
{
if(k!=3)
ok=0;
else
{
int fd=0;
for(auto v:pt[i])
{
if(v.size()==1)
tag[v[0]]=1;
else
{
if(fd<2)
{
fd++;
tag[v[0]]=1;
}
else
{
for(auto x:v)
tag[x]=1;
}
}
}
if(fd<2)
ok=0;
}
++c3;
}
else
ok=0;
}
ok&=c2<=2;
ok&=c3<=1;
if(!ok)
{
cout<<"No\n";
continue;
}
// for(int i = 1;i <= n;i++) {
// if(!tag[i]) printf("tg %d\n",i) ;
// }
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: 1ms
memory: 5880kb
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: 0
Accepted
time: 1ms
memory: 3628kb
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 Yes Yes Yes Yes Yes No No No No Yes No No No No No No No No Yes No No No No No No No No
result:
ok 31 tokens
Test #3:
score: 0
Accepted
time: 46ms
memory: 5688kb
input:
8018 26 28 3 24 5 10 24 3 10 21 3 15 21 11 15 6 11 12 6 11 19 19 1 1 26 26 8 8 23 23 7 7 8 12 2 2 16 16 20 20 25 25 9 9 13 13 20 11 22 22 17 17 14 14 18 18 4 4 22 19 21 3 17 14 1 17 13 1 15 13 4 15 8 4 13 19 19 18 18 2 2 19 13 6 6 5 5 11 11 10 10 6 1 12 12 7 7 9 9 16 16 3 3 12 23 25 3 18 8 5 18 1 5 ...
output:
No No Yes No No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes No Yes Yes No Yes No Yes Yes Yes Yes No Yes No No Yes No No Yes Yes Yes Yes No Yes Yes Yes No No Yes Yes Yes Yes No Yes Yes No Yes No Yes Yes No No Yes No Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Y...
result:
ok 8018 tokens
Test #4:
score: 0
Accepted
time: 52ms
memory: 5768kb
input:
5714 36 38 3 6 13 27 6 15 27 28 15 25 28 35 25 21 35 19 21 14 19 24 14 12 24 27 34 34 29 29 5 5 11 11 20 20 1 1 26 26 20 25 18 18 32 32 36 36 31 31 17 17 30 30 22 22 8 8 3 3 30 24 10 10 9 9 4 4 2 2 33 33 7 7 16 16 4 12 23 38 40 3 9 15 38 9 35 38 2 35 4 2 28 4 5 28 8 5 20 8 37 20 34 37 27 34 36 27 3 ...
output:
Yes Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes Yes No Yes Yes Yes Yes No No Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes No Yes No Yes No Yes No No Yes Yes Yes Yes No Yes Yes No Yes Yes No Yes Yes Yes No Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No No Yes Yes No Yes Yes Yes Yes Ye...
result:
ok 5714 tokens
Test #5:
score: 0
Accepted
time: 54ms
memory: 5900kb
input:
4447 46 48 3 10 39 23 10 16 23 2 16 44 2 41 44 40 41 46 40 37 46 26 37 1 26 22 1 45 22 6 45 9 6 20 9 35 20 7 35 11 7 17 11 19 17 14 19 4 14 28 4 7 15 15 3 3 27 27 15 41 21 21 43 43 42 42 12 12 24 24 36 36 5 5 18 18 38 38 34 34 32 32 13 13 38 44 33 33 29 29 31 31 30 30 25 25 33 28 8 46 48 3 29 22 14 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes No No Yes Yes Yes No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes No Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes No Yes Yes ...
result:
ok 4447 tokens
Test #6:
score: 0
Accepted
time: 61ms
memory: 3768kb
input:
1324 188 190 3 54 144 146 54 175 146 21 175 158 21 95 158 171 95 169 171 141 169 70 141 102 70 19 102 4 19 159 4 24 159 88 24 15 88 139 15 118 139 27 118 112 27 132 112 125 132 80 125 83 80 58 83 179 58 186 179 73 186 108 73 56 108 173 56 82 173 152 82 153 152 160 153 128 160 90 128 116 90 124 116 4...
output:
Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes...
result:
ok 1324 tokens
Test #7:
score: 0
Accepted
time: 76ms
memory: 4448kb
input:
134 1410 1412 3 106 27 458 106 782 458 1310 782 1125 1310 978 1125 321 978 24 321 619 24 86 619 617 86 320 617 1098 320 1128 1098 718 1128 620 718 256 620 865 256 1405 865 878 1405 875 878 242 875 873 242 131 873 1007 131 389 1007 1117 389 651 1117 1102 651 546 1102 65 546 81 65 1388 81 752 1388 728...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 134 tokens
Test #8:
score: 0
Accepted
time: 109ms
memory: 10640kb
input:
12 11985 11987 3 11734 6512 1902 11734 9252 1902 9820 9252 8101 9820 3603 8101 7558 3603 7842 7558 10845 7842 9298 10845 1375 9298 9762 1375 9267 9762 4646 9267 1016 4646 4128 1016 8809 4128 11051 8809 6272 11051 8985 6272 9486 8985 6734 9486 1875 6734 6762 1875 11836 6762 6299 11836 10083 6299 1134...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
result:
ok 12 tokens
Test #9:
score: 0
Accepted
time: 94ms
memory: 35888kb
input:
1 108420 108422 3 107664 11603 1478 107664 19044 1478 53540 19044 105029 53540 24800 105029 26109 24800 107534 26109 100472 107534 66646 100472 80884 66646 98924 80884 47833 98924 60451 47833 108061 60451 8683 108061 50909 8683 68228 50909 42038 68228 74380 42038 6647 74380 48902 6647 47084 48902 26...
output:
Yes
result:
ok "Yes"
Test #10:
score: 0
Accepted
time: 50ms
memory: 5740kb
input:
8002 21 23 3 13 14 7 13 12 7 11 12 7 3 3 2 2 5 5 3 13 15 15 18 18 20 20 9 9 15 11 8 8 10 10 21 21 1 1 16 16 4 4 10 11 6 6 17 17 19 25 27 3 23 24 8 23 21 8 3 21 11 3 19 11 10 19 21 17 17 12 12 15 15 5 5 25 25 2 2 1 1 25 19 9 9 13 13 4 4 20 20 9 11 6 6 18 18 14 14 22 22 7 7 16 16 18 19 21 3 16 19 2 16...
output:
Yes Yes Yes Yes Yes Yes No No Yes Yes No Yes Yes No No Yes Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes No No No Yes No No No No No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes No No Yes No No Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes No Yes Yes No Yes Y...
result:
ok 8002 tokens
Test #11:
score: 0
Accepted
time: 48ms
memory: 5968kb
input:
5702 34 36 3 8 22 19 8 23 19 5 23 3 5 26 3 29 26 34 29 29 14 14 27 27 9 9 28 28 13 13 16 16 1 1 32 32 20 20 21 21 24 24 15 15 11 11 7 7 6 6 4 4 7 5 33 33 2 2 10 10 18 18 33 5 31 31 30 30 17 17 12 12 25 25 31 33 37 5 10 12 21 10 27 21 31 27 1 31 10 19 19 30 30 23 23 7 7 30 27 5 5 15 15 17 17 26 26 25...
output:
No No Yes Yes Yes No No No Yes Yes Yes Yes Yes Yes No No Yes Yes Yes Yes No No Yes Yes Yes Yes No Yes No Yes Yes No No No No Yes Yes No Yes Yes Yes No Yes Yes No No Yes No No Yes No No No Yes Yes Yes No No No Yes Yes No Yes No Yes Yes No Yes No No No No No Yes Yes No Yes No No Yes No Yes No Yes No Y...
result:
ok 5702 tokens
Test #12:
score: 0
Accepted
time: 50ms
memory: 5644kb
input:
4441 39 41 3 23 8 1 23 25 1 35 25 22 35 19 22 31 19 17 31 18 17 32 18 28 32 24 28 38 24 27 38 11 27 29 11 15 29 9 15 14 9 20 14 15 2 2 10 10 30 30 33 33 3 3 26 26 4 4 16 16 36 36 4 22 13 13 39 39 7 7 12 12 13 8 34 34 6 6 21 21 5 5 37 37 34 45 48 4 13 17 18 13 20 18 39 20 4 39 24 4 41 24 43 41 8 43 3...
output:
Yes Yes Yes Yes No No Yes Yes Yes No No Yes Yes No Yes Yes Yes Yes No No Yes No No No Yes No Yes No Yes Yes No Yes Yes Yes No No No Yes Yes No No No Yes No Yes Yes No Yes Yes No No No Yes No Yes Yes No Yes Yes No Yes No Yes No Yes No No Yes No No Yes Yes Yes Yes Yes Yes Yes Yes No Yes No Yes No No N...
result:
ok 4441 tokens
Test #13:
score: 0
Accepted
time: 53ms
memory: 5704kb
input:
1334 192 196 5 130 167 143 130 36 143 144 36 152 144 50 152 83 50 110 83 70 110 150 70 162 150 189 162 161 189 177 161 118 177 51 118 6 51 169 6 67 169 45 67 9 45 58 9 129 58 50 92 92 135 135 61 61 158 158 65 65 55 55 4 4 163 163 81 81 106 106 184 184 2 2 41 41 15 15 3 3 75 75 148 148 127 127 31 31 ...
output:
Yes Yes No Yes No Yes No Yes No Yes No Yes Yes Yes No No No Yes No Yes No Yes Yes Yes No No Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes No No Yes Yes Yes No Yes No Yes Yes Yes Yes No Yes No Yes No Yes No No Yes Yes Yes Yes Yes No Yes No No Y...
result:
ok 1334 tokens
Test #14:
score: 0
Accepted
time: 61ms
memory: 6324kb
input:
133 1906 1932 27 1870 1737 332 1870 142 332 1293 142 1802 1293 1738 1802 524 1738 81 524 1177 81 1014 1177 498 1014 649 498 368 649 9 368 1164 9 1717 1164 1441 1717 1479 1441 1180 1479 747 1180 15 747 292 15 566 292 1410 566 1827 1410 1289 1827 1697 1289 570 1697 830 570 1628 830 1228 1628 1248 1228...
output:
Yes Yes No Yes No Yes Yes Yes No Yes Yes Yes No No Yes No Yes Yes No Yes Yes Yes Yes Yes Yes No No No No Yes No Yes No Yes No No No Yes No No Yes No Yes Yes No Yes Yes Yes Yes Yes Yes Yes Yes No No No Yes No No Yes Yes No Yes Yes Yes No No No Yes Yes Yes Yes Yes No Yes Yes No No No No Yes Yes Yes Ye...
result:
ok 133 tokens
Test #15:
score: 0
Accepted
time: 89ms
memory: 11556kb
input:
13 12586 12608 23 7533 7649 10087 7533 6434 10087 11855 6434 2721 11855 2107 2721 2506 2107 2433 2506 1584 2433 12443 1584 8461 12443 9537 8461 7168 9537 4582 7168 5270 4582 711 5270 3174 711 5259 3174 2058 5259 12168 2058 10935 12168 2349 10935 1437 2349 1294 1437 5298 1294 12512 5298 2662 12512 10...
output:
Yes Yes No Yes Yes Yes No No No Yes No Yes Yes
result:
ok 13 tokens
Test #16:
score: 0
Accepted
time: 65ms
memory: 19360kb
input:
1 143811 144013 203 49366 8334 101085 49366 113368 101085 3777 113368 124696 3777 91966 124696 66250 91966 108815 66250 7414 108815 53505 7414 78360 53505 7910 78360 42943 7910 42229 42943 47844 42229 71780 47844 5981 71780 46950 5981 74305 46950 7631 74305 82674 7631 105722 82674 101150 105722 1038...
output:
No
result:
ok "No"
Test #17:
score: -100
Time Limit Exceeded
input:
8018 113379 28 3 24465 31311 78654 89409 8778 98104 90920 50695 8039 97335 65866 5544 44900 14267 58604 59700 71505 61152 103401 99870 14403 10098 99282 110230 53671 6681 40824 89753 63973 104145 95214 30781 8833 18000 104982 51016 4407 110937 54233 55440 101355 8737 29341 35509 41957 79895 110512 4...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...