QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107051 | #5307. Subgraph Isomorphism | SmallBlack | WA | 144ms | 19824kb | C++14 | 2.3kb | 2023-05-20 09:51:21 | 2023-10-15 17:25:23 |
Judging History
answer
// Problem: D - Subgraph Isomorphism
// Contest: Virtual Judge - 过什么520做题要紧
// URL: https://vjudge.net/contest/559671#problem/D
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Date:2023-05-20 07:53:15
// By:SmallBlack
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long s=0,k=1;
char c=getchar();
while(!isdigit(c))
{
k=(c=='-')?-1:1;
c=getchar();
}
while(isdigit(c))
{
s=s*10+c-'0';
c=getchar();
}
return s*k;
}
#define d read()
#define ll long long
#define ull unsigned long long
#define Maxn 10010
#define Size 100010
#define mp make_pair
#define pb push_back
#define fi first
#define se second
vector<ll>e[Size];
vector<ll>st,loop,LP;
bool ins[Size],fin=0;
void dfs(ll u,ll fa)
{
ins[u]=1,st.pb(u);
for(auto v:e[u])
{
if(v==fa) continue;
if(ins[v])
{
while(st.back()!=v)
{
loop.pb(st.back());
st.pop_back();
}
loop.pb(v);
fin=1;
return;
}
dfs(v,u);
if(fin) return;
}
st.pop_back(),ins[u]=0;
}
#define mod 1000000000000002493
ll ksm(ll x,int y)
{
ll ans=1;
while(y)
{
if(y&1) ans=(__int128)ans*x%mod;
y>>=1,x=(__int128)x*x%mod;
}
return ans;
}
ll tag[Size];
void Hash(ll u,ll fa)
{
tag[u]=1;
for(auto v:e[u])
{
if(v==fa||ins[v]) continue;
Hash(v,u);
tag[u]+=ksm(tag[v],131);
}
}
void solve()
{
ll n=d,m=d;
for(int i=1;i<=n;i++) e[i].clear(),ins[i]=0,tag[i]=0;
for(int i=0;i<m;i++)
{
ll x=d,y=d;
e[x].pb(y),e[y].pb(x);
}
if(m==n-1) return (void)puts("YES");
else if(m>n) return (void)puts("NO");
fin=0,st.clear(),loop.clear(),dfs(1,0);
for(int i=1;i<=n;i++) ins[i]=0;
for(auto x:loop) ins[x]=1;
if(loop.size()==n) return (void)puts("YES");
LP.clear();
for(int i=0;i<loop.size();i++)
if(e[loop[i]].size()>2) Hash(loop[i],0),LP.pb(i);
if(LP.size()<2) return (void)puts("NO");
if(LP[1]-LP[0]>2) return (void)puts("NO");
if(LP[0]+loop.size()-LP[LP.size()-1]!=LP[1]-LP[0])
return (void)puts("NO");
for(int i=2;i<LP.size();i++)
if(LP[i]-LP[i-1]!=LP[1]-LP[0])
return (void)puts("NO");
for(int i=1;i<LP.size();i++)
if(tag[loop[LP[i]]]!=tag[loop[LP[0]]])
return (void)puts("NO");
puts("YES");
}
int main()
{
ll t=d;
while(t--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5776kb
input:
4 7 6 1 2 2 3 3 4 4 5 5 6 3 7 3 3 1 2 2 3 3 1 5 5 1 2 2 3 3 4 4 1 1 5 1 0
output:
YES YES NO YES
result:
ok 4 token(s): yes count is 3, no count is 1
Test #2:
score: 0
Accepted
time: 10ms
memory: 5760kb
input:
33192 2 1 1 2 3 2 1 3 2 3 3 3 1 2 1 3 2 3 4 3 1 4 2 4 3 4 4 3 1 3 1 4 2 4 4 4 1 3 1 4 2 4 3 4 4 4 1 3 1 4 2 3 2 4 4 5 1 3 1 4 2 3 2 4 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 5 4 1 5 2 5 3 5 4 5 5 4 1 4 1 5 2 5 3 5 5 5 1 4 1 5 2 5 3 5 4 5 5 5 1 4 1 5 2 4 3 5 4 5 5 5 1 4 1 5 2 4 2 5 3 5 5 6 1 4 1 5 2 4 2 5 3 ...
output:
YES YES YES YES YES NO YES NO NO YES YES NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO NO NO NO YES YES NO YES YES NO NO NO YES NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 33192 token(s): yes count is 58, no count is 33134
Test #3:
score: 0
Accepted
time: 13ms
memory: 5824kb
input:
40000 9 24 1 4 1 6 1 7 1 9 2 5 2 7 2 8 2 9 3 5 3 7 3 8 3 9 4 6 4 8 4 9 5 6 5 8 5 9 6 7 6 8 6 9 7 8 7 9 8 9 9 21 1 4 1 6 1 7 1 8 2 5 2 7 2 8 2 9 3 5 3 7 3 9 4 6 4 8 4 9 5 6 5 9 6 7 6 8 6 9 7 8 8 9 9 21 1 4 1 6 1 7 1 8 2 5 2 7 2 8 2 9 3 5 3 7 3 9 4 6 4 8 4 9 5 6 5 9 6 7 6 8 6 9 7 8 7 9 9 22 1 4 1 6 1 ...
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 ...
result:
ok 40000 token(s): yes count is 0, no count is 40000
Test #4:
score: 0
Accepted
time: 11ms
memory: 5848kb
input:
40000 9 16 1 4 1 6 1 8 1 9 2 5 2 7 2 8 2 9 3 6 3 7 4 7 5 8 6 9 7 8 7 9 8 9 9 16 1 4 1 6 1 8 1 9 2 5 2 7 2 8 2 9 3 6 3 7 4 7 5 8 5 9 7 8 7 9 8 9 9 16 1 4 1 6 1 8 1 9 2 5 2 7 2 8 2 9 3 6 3 7 4 7 5 8 5 9 6 9 7 8 8 9 9 16 1 4 1 6 1 8 1 9 2 5 2 7 2 8 2 9 3 6 3 7 4 7 5 8 5 9 6 9 7 8 7 9 9 17 1 4 1 6 1 8 1...
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 ...
result:
ok 40000 token(s): yes count is 0, no count is 40000
Test #5:
score: 0
Accepted
time: 7ms
memory: 5852kb
input:
40000 9 17 1 5 1 6 1 7 1 8 2 5 2 7 2 9 3 6 3 8 3 9 4 7 4 8 4 9 5 7 5 8 5 9 6 9 9 18 1 5 1 6 1 7 1 8 2 5 2 7 2 9 3 6 3 8 3 9 4 7 4 8 4 9 5 7 5 8 5 9 6 9 8 9 9 18 1 5 1 6 1 7 1 8 2 5 2 7 2 9 3 6 3 8 3 9 4 7 4 8 4 9 5 7 5 8 5 9 6 9 7 9 9 19 1 5 1 6 1 7 1 8 2 5 2 7 2 9 3 6 3 8 3 9 4 7 4 8 4 9 5 7 5 8 5 ...
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 ...
result:
ok 40000 token(s): yes count is 0, no count is 40000
Test #6:
score: 0
Accepted
time: 7ms
memory: 5820kb
input:
40000 9 17 1 5 1 6 1 7 1 8 2 6 2 7 2 8 2 9 3 7 3 9 4 9 5 8 6 7 6 8 6 9 7 9 8 9 9 16 1 5 1 6 1 7 1 8 2 6 2 7 2 8 2 9 3 7 3 9 4 9 5 8 5 9 6 7 6 8 8 9 9 16 1 5 1 6 1 7 1 8 2 6 2 7 2 8 2 9 3 7 3 9 4 9 5 8 5 9 6 7 6 8 7 9 9 17 1 5 1 6 1 7 1 8 2 6 2 7 2 8 2 9 3 7 3 9 4 9 5 8 5 9 6 7 6 8 7 9 8 9 9 17 1 5 1...
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 ...
result:
ok 40000 token(s): yes count is 0, no count is 40000
Test #7:
score: 0
Accepted
time: 6ms
memory: 6488kb
input:
40000 9 15 1 5 1 8 1 9 2 6 2 7 2 9 3 6 3 7 4 7 4 8 4 9 5 8 6 9 7 9 8 9 9 13 1 5 1 8 1 9 2 6 2 7 2 9 3 6 3 7 4 7 4 8 4 9 5 8 5 9 9 14 1 5 1 8 1 9 2 6 2 7 2 9 3 6 3 7 4 7 4 8 4 9 5 8 5 9 8 9 9 14 1 5 1 8 1 9 2 6 2 7 2 9 3 6 3 7 4 7 4 8 4 9 5 8 5 9 7 9 9 15 1 5 1 8 1 9 2 6 2 7 2 9 3 6 3 7 4 7 4 8 4 9 5...
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 ...
result:
ok 40000 token(s): yes count is 1, no count is 39999
Test #8:
score: 0
Accepted
time: 6ms
memory: 5756kb
input:
40000 9 8 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 1 8 1 9 2 9 3 9 4 9 5 9 6 9 7 9 9 9 1 8 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 1 8 2 8 3 9 4 9 5 9 6 9 7 9 8 9 9 8 1 8 1 9 2 8 3 9 4 9 5 9 6 9 7 9 9 9 1 8 1 9 2 8 3 9 4 9 5 9 6 9 7 9 8 9 9 9 1 8 1 9 2 8 2 9 3 9 4 9 5 9 6 9 7 9 9 10 1 8 1 9 2 8 2 9 3 9 4 9 5...
output:
YES YES NO YES YES NO NO NO YES YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO YES NO NO NO NO NO NO NO YES NO YES 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 YES NO YES NO NO NO N...
result:
ok 40000 token(s): yes count is 50, no count is 39950
Test #9:
score: 0
Accepted
time: 8ms
memory: 6588kb
input:
1393 25 100 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 3 2 4 2 5 2 10 2 11 2 12 2 13 3 4 3 5 3 14 3 17 3 18 3 19 4 5 4 15 4 20 4 22 4 23 5 16 5 21 5 24 5 25 6 7 6 8 6 9 6 10 6 14 6 15 6 16 7 8 7 9 7 11 7 17 7 20 7 21 8 9 8 12 8 18 8 22 8 24 9 13 9 19 9 23 9 25 10 11 10 12 10 13 10 14 10 15 10 16 11 12 11 13 ...
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 ...
result:
ok 1393 token(s): yes count is 0, no count is 1393
Test #10:
score: 0
Accepted
time: 11ms
memory: 6416kb
input:
3000 35 280 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 2 3 2 4 2 5 2 6 2 7 2 8 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 3 11 3 12 3 13 3 16 3 17 3 18 3 21 3 24 3 25 3 26 3 27 3 32 3 34 3 35 4 10 4 14 4 15 4 16 4 17 4 19 4 20 4 24 4 25 4 26 4 28 4 31 4 33 4 35 5 9 5 1...
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 ...
result:
ok 3000 token(s): yes count is 0, no count is 3000
Test #11:
score: 0
Accepted
time: 129ms
memory: 13412kb
input:
30 28171 28170 2482 5158 15414 17513 7825 17196 10171 8545 8850 13596 3314 9296 5490 15625 18905 9569 24135 6453 360 718 65 27875 13734 20008 20072 4447 23395 24852 11440 1818 20672 13049 13770 6079 19115 24044 22134 24300 15787 3053 6462 6652 3200 14184 20621 629 1328 5200 7181 17707 4515 18911 249...
output:
YES NO NO NO YES YES NO NO NO NO YES NO NO NO YES YES YES NO YES NO NO NO NO NO YES YES NO NO YES YES
result:
ok 30 token(s): yes count is 12, no count is 18
Test #12:
score: 0
Accepted
time: 144ms
memory: 12144kb
input:
30 3658 3658 1673 1805 115 1360 145 1722 3398 2869 700 3578 2145 60 3563 2682 2957 307 2443 1048 3581 2555 2368 2336 1023 3041 664 412 1950 552 3425 1162 3159 3296 1373 1763 1336 3591 1119 1992 1912 354 3573 3124 1351 1022 3047 2879 2521 1939 1683 1679 1070 1259 1342 1637 732 2576 2167 3067 2742 514...
output:
NO NO YES YES NO YES YES NO NO NO YES NO NO NO YES NO YES YES NO YES NO YES NO YES NO YES YES NO NO NO
result:
ok 30 token(s): yes count is 13, no count is 17
Test #13:
score: 0
Accepted
time: 105ms
memory: 12148kb
input:
30 6200 6199 2543 3295 1003 4780 4627 4563 5620 660 1731 3047 1198 3343 3419 4710 2488 3843 3722 4576 752 3212 5313 4025 4612 286 1967 1397 36 2212 1206 928 4689 1268 2831 4376 4334 3028 1040 1514 5636 5331 4257 571 5182 5007 1629 208 2345 3406 5280 4999 2607 2254 6192 1403 5075 3889 3389 5294 3682 ...
output:
YES NO YES YES YES NO YES NO NO NO YES NO NO YES NO YES NO NO YES YES YES NO NO YES YES YES NO YES NO YES
result:
ok 30 token(s): yes count is 16, no count is 14
Test #14:
score: 0
Accepted
time: 119ms
memory: 12468kb
input:
30 14491 14490 6052 10994 13301 461 1336 9631 10722 4121 9829 5812 11883 5039 4854 6739 4064 11033 466 6698 2959 4374 3041 3663 5616 3289 458 788 4018 8915 13689 2763 14153 14146 2336 9011 7827 11114 9235 13235 4091 5135 8099 10920 4359 13623 10194 870 3222 11124 13620 2624 4477 7638 12926 10795 506...
output:
YES YES NO NO YES NO NO NO YES NO YES NO YES YES YES YES NO NO YES YES YES YES YES YES YES YES NO YES NO NO
result:
ok 30 token(s): yes count is 18, no count is 12
Test #15:
score: 0
Accepted
time: 124ms
memory: 17184kb
input:
30 100000 99999 58634 53166 60069 39545 82578 88227 56874 85747 22905 28646 92672 64752 22373 59305 22541 59348 44095 65942 4988 67515 10343 77755 60473 69842 23600 65125 30620 9705 23682 88606 90443 30376 64660 28469 49987 74473 95538 6848 57849 92719 41776 11339 34932 41927 53269 36288 27451 77680...
output:
YES NO YES NO YES NO YES NO YES NO NO YES NO NO YES YES NO NO NO YES YES NO NO NO NO NO NO NO YES YES
result:
ok 30 token(s): yes count is 12, no count is 18
Test #16:
score: 0
Accepted
time: 94ms
memory: 19824kb
input:
30 28822 28821 18849 2213 3904 10406 22000 14733 3382 11686 18120 2209 16720 21313 27796 11273 2151 1627 14221 1730 28679 13010 13611 8540 8923 13036 14093 25113 28268 1341 22450 5687 24407 28379 28185 19130 9949 4590 19825 24477 24266 21368 15658 20039 19834 22900 10711 27768 21931 21505 701 5260 2...
output:
YES NO YES YES NO YES YES YES NO NO NO NO NO NO YES NO NO YES YES YES NO NO YES NO NO YES YES NO NO YES
result:
ok 30 token(s): yes count is 14, no count is 16
Test #17:
score: 0
Accepted
time: 87ms
memory: 19360kb
input:
30 94155 94155 59782 9369 85417 55440 49151 38561 70569 2997 58372 92455 55440 13968 23987 25454 31693 59782 28401 47143 70435 87698 29557 80207 71824 24642 52316 53847 52316 49058 26005 29924 42139 19301 57171 76189 41506 59782 41871 88927 2997 10080 41910 83200 52724 3425 55302 18910 72572 45110 6...
output:
NO YES NO YES YES NO YES NO NO YES YES NO YES NO YES NO YES YES NO YES YES YES NO NO YES NO NO NO NO NO
result:
ok 30 token(s): yes count is 14, no count is 16
Test #18:
score: -100
Wrong Answer
time: 51ms
memory: 5784kb
input:
100000 8 8 7 6 2 8 4 2 7 1 4 3 7 2 6 3 5 6 19 18 7 19 17 10 16 2 1 17 9 2 13 18 8 13 1 6 2 5 5 3 14 5 15 7 2 13 13 7 2 4 2 12 11 7 13 6 36 35 32 14 3 19 9 27 31 20 3 13 3 20 7 8 20 6 28 33 24 5 17 20 12 20 11 24 18 16 25 20 10 30 36 16 15 3 2 16 21 28 21 24 24 12 34 25 17 1 11 2 6 27 29 7 26 20 5 23...
output:
NO YES YES YES YES YES NO YES YES NO NO YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES YES NO YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES YES YES NO NO YES YES YES NO YES YES YES NO NO YES YES NO YES NO NO YES NO YES NO YES NO NO YES YES YES YES YES YES ...
result:
wrong answer expected YES, found NO [94201st token]