QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#392838 | #4000. Dynamic Reachability | Flamire | AC ✓ | 6701ms | 78068kb | C++17 | 3.3kb | 2024-04-17 21:13:09 | 2024-04-17 21:13:10 |
Judging History
answer
#include <bits/stdc++.h>
#define N 100011
using namespace std;
int n,m,q,U[N],V[N];
const int B=64;
bitset<2*B> to[2*B],nto[2*B];
vector<int> G[N],E[N];
int cmd[N][5],blk[N],bl[N],br[N],id[N];
bitset<2*B> mset[N];
int dfn[N],low[N],clk,stk[N],nscc,scc[N];bool vis[N];
void tarjan(int u)
{//printf("tarjan(%d)\n",u);
dfn[u]=low[u]=++clk;vis[u]=1;stk[++stk[0]]=u;
for(int v:G[u])
{
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++nscc;scc[u]=nscc;vis[u]=0;
while(stk[stk[0]]!=u)scc[stk[stk[0]]]=nscc,vis[stk[stk[0]]]=0,--stk[0];
--stk[0];
}
}
int Q[N],ql,qr;
bitset<2*B> ok;
vector<int> vb,ve;
void bfs(int u)
{//printf("--------------------bfs(%d)\n",u);
ql=qr=0;Q[qr++]=u;
ok.reset();ok[u]=1;
while(ql^qr)
{
int p=Q[ql++];//printf("p:%d\n",p);
bitset<2*B> nw=nto[p]&~ok;
// printf("nw:");for(int i=0;i<n;++i)printf("%d",(int)nw[i]);putchar(10);
int id;
while((id=nw._Find_first())<vb.size())ok[id]=1,Q[qr++]=id,nw[id]=0;
}
}
bool cur[N],ine[N];
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;++i)
{
int u,v;scanf("%d%d",&u,&v);U[i]=u;V[i]=v;
G[u].push_back(v);
}
for(int i=1;i<=q;++i)
{
int a,b,c;
scanf("%d%d",&a,&b);
if(a==1)
{
cmd[i][0]=a,cmd[i][1]=U[b],cmd[i][2]=V[b],cmd[i][4]=b;
}
else cmd[i][0]=a,cmd[i][1]=b,scanf("%d",cmd[i]+2);
}
for(int i=1;i<=q;++i)blk[i]=(i-1)/B+1;
for(int i=1;i<=blk[q];++i)bl[i]=(i-1)*B+1,br[i]=min(i*B,q);
for(int i=1;i<=m;++i)cur[i]=1;
for(int $=1;$<=(q-1)/B+1;++$)
{//printf("=============================================[%d,%d]\n",bl[$],br[$]);
vb.clear();ve.clear();
for(int i=1;i<=m;++i)ine[i]=0;
for(int i=1;i<=n;++i)id[i]=-1;
for(int j=bl[$];j<=br[$];++j)
{
if(!~id[cmd[j][1]])vb.push_back(cmd[j][1]),id[cmd[j][1]]=vb.size()-1;
if(!~id[cmd[j][2]])vb.push_back(cmd[j][2]),id[cmd[j][2]]=vb.size()-1;
if(cmd[j][0]==1&&!ine[cmd[j][4]])ve.push_back(cmd[j][4]),ine[cmd[j][4]]=1;
}
// printf("b:");for(int x:vb)printf("%d ",x);putchar(10);
// printf("e:");for(int e:ve)printf("%d ",e);putchar(10);
for(int u=1;u<=n;++u)G[u].clear();
for(int i=1;i<=m;++i)if(cur[i]&&!ine[i])G[U[i]].push_back(V[i]);
for(int i=1;i<=n;++i)dfn[i]=0;clk=nscc=stk[0]=0;
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
// printf("scc:");for(int i=1;i<=n;++i)printf("%d ",scc[i]);putchar(10);
for(int i=1;i<=nscc;++i)E[i].clear();
for(int i=1;i<=m;++i)if(cur[i]&&!ine[i]&&scc[U[i]]!=scc[V[i]])E[scc[U[i]]].push_back(scc[V[i]]);
for(int i=1;i<=nscc;++i)mset[i].reset();
for(int i=0;i<vb.size();++i)mset[scc[vb[i]]][i]=1;
for(int i=1;i<=nscc;++i)
{
for(int v:E[i])mset[i]|=mset[v];
}
for(int i=0;i<vb.size();++i)
{
for(int j=0;j<vb.size();++j)to[i][j]=mset[scc[vb[i]]][j];
}
// printf("to:\n");
// for(int i=0;i<vb.size();++i)
// {
// for(int j=0;j<vb.size();++j)printf("%d ",(int)to[i][j]);putchar(10);
// }
for(int i=bl[$];i<=br[$];++i)
{
if(cmd[i][0]==1)cur[cmd[i][4]]^=1;
else
{
for(int u=0;u<vb.size();++u)nto[u]=to[u];
for(int e:ve)if(cur[e])nto[id[U[e]]][id[V[e]]]=1;
bfs(id[cmd[i][1]]);
printf(ok[id[cmd[i][2]]]?"YES\n":"NO\n");
}
}
}
fclose(stdin);fclose(stdout);return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 15264kb
input:
5 6 7 1 2 1 3 2 4 3 4 3 5 4 5 2 1 5 2 2 3 1 3 1 4 2 1 4 1 3 2 1 5
output:
YES NO NO YES
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 5839ms
memory: 21568kb
input:
50000 100000 100000 36671 44121 25592 44321 13226 46463 13060 25694 14021 20087 22881 38333 34655 47774 22868 26462 31154 48710 27491 32365 5874 47497 17622 28600 1886 14193 22315 23656 14973 22704 1335 25384 22612 34915 2852 48213 23334 25519 24342 28784 6238 36125 14598 39494 33069 34250 2123 3059...
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 50000 lines
Test #3:
score: 0
Accepted
time: 5814ms
memory: 21404kb
input:
50000 100000 100000 27059 36120 32335 41190 9436 29046 36520 44281 25005 39115 37096 43321 11891 38873 10439 31878 19154 25918 26756 44170 9594 16092 9920 23747 17107 35055 31401 35308 17102 35604 18635 26767 27925 29726 7012 14266 973 21483 622 41029 25685 31856 36951 46699 18103 46885 9911 18465 2...
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 50000 lines
Test #4:
score: 0
Accepted
time: 6465ms
memory: 18612kb
input:
50000 100000 100000 7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 77 77 84 84 91 91 98 98 105 105 112 112 119 119 126 126 133 133 140 140 147 147 154 154 161 161 168 168 175 175 182 182 189 189 196 196 203 203 210 210 217 217 224 224 231 231 238 238 245 245 252 252 259 259 266 266 273 273 ...
output:
NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO YES 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 NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO N...
result:
ok 100000 lines
Test #5:
score: 0
Accepted
time: 5811ms
memory: 21144kb
input:
50000 100000 100000 233 466 466 699 699 932 932 1165 1165 1398 1398 1631 1631 1864 1864 2097 2097 2330 2330 2563 2563 2796 2796 3029 3029 3262 3262 3495 3495 3728 3728 3961 3961 4194 4194 4427 4427 4660 4660 4893 4893 5126 5126 5359 5359 5592 5592 5825 5825 6058 6058 6291 6291 6524 6524 6757 6757 69...
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 50000 lines
Test #6:
score: 0
Accepted
time: 5888ms
memory: 21136kb
input:
50000 100000 100000 13 26 26 39 39 52 52 65 65 78 78 91 91 104 104 117 117 130 130 143 143 156 156 169 169 182 182 195 195 208 208 221 221 234 234 247 247 260 260 273 273 286 286 299 299 312 312 325 325 338 338 351 351 364 364 377 377 390 390 403 403 416 416 429 429 442 442 455 455 468 468 481 481 4...
output:
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 NO NO YES 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 NO NO NO 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 YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 50000 lines
Test #7:
score: 0
Accepted
time: 5941ms
memory: 21292kb
input:
50000 100000 100000 4 8 8 12 12 16 16 20 20 24 24 28 28 32 32 36 36 40 40 44 44 48 48 52 52 56 56 60 60 64 64 68 68 72 72 76 76 80 80 84 84 88 88 92 92 96 96 100 100 104 104 108 108 112 112 116 116 120 120 124 124 128 128 132 132 136 136 140 140 144 144 148 148 152 152 156 156 160 160 164 164 168 16...
output:
YES YES NO NO NO NO NO YES YES 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 NO YES YES NO NO YES NO NO NO NO NO YES YES NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO YES NO YES YES NO NO YES NO YES YES NO NO YES NO NO YES NO NO NO NO NO N...
result:
ok 50000 lines
Test #8:
score: 0
Accepted
time: 5857ms
memory: 22024kb
input:
50000 100000 100000 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98...
output:
NO NO NO NO NO NO YES YES YES YES NO YES YES YES NO NO YES YES NO NO NO NO YES NO YES YES NO YES NO YES YES NO NO YES YES YES NO YES YES NO NO YES YES YES NO NO YES NO YES NO NO NO YES YES YES NO YES NO NO YES YES YES YES YES YES NO NO YES NO NO YES NO YES YES NO NO NO NO YES NO NO NO YES YES NO YES...
result:
ok 50000 lines
Test #9:
score: 0
Accepted
time: 5480ms
memory: 22512kb
input:
50000 100000 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 ...
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 50000 lines
Test #10:
score: 0
Accepted
time: 5349ms
memory: 21496kb
input:
50000 100000 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 ...
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 NO YES YES YES YES YES YES YES YES NO NO YES YES YES YES YES NO YES YES YES YES YES YES YES YES NO NO NO YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES NO YES YES YES YES YES YE...
result:
ok 50000 lines
Test #11:
score: 0
Accepted
time: 5502ms
memory: 20272kb
input:
50000 100000 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 ...
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 NO NO YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES Y...
result:
ok 50000 lines
Test #12:
score: 0
Accepted
time: 5791ms
memory: 20112kb
input:
50000 100000 100000 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 10 11 12 13 13 14 14 15 15 16 16 17 18 19 19 20 20 21 21 22 22 23 24 25 25 26 26 27 27 28 28 29 30 31 31 32 32 33 33 34 34 35 36 37 37 38 38 39 39 40 40 41 42 43 43 44 44 45 45 46 46 47 48 49 49 50 50 51 51 52 52 53 54 55 55 56 56 57 57 58 58 59 6...
output:
YES NO NO NO 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 NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 50000 lines
Test #13:
score: 0
Accepted
time: 4497ms
memory: 24480kb
input:
50000 100000 100000 12500 12501 12501 12502 12502 12503 12503 12504 12504 12505 12505 12506 12506 12507 12507 12508 12508 12509 12509 12510 12510 12511 12511 12512 12512 12513 12513 12514 12514 12515 12515 12516 12516 12517 12517 12518 12518 12519 12519 12520 12520 12521 12521 12522 12522 12523 1252...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 50000 lines
Test #14:
score: 0
Accepted
time: 4497ms
memory: 24212kb
input:
50000 100000 100000 12500 12501 12501 12502 12502 12503 12503 12504 12504 12505 12505 12506 12506 12507 12507 12508 12508 12509 12509 12510 12510 12511 12511 12512 12512 12513 12513 12514 12514 12515 12515 12516 12516 12517 12517 12518 12518 12519 12519 12520 12520 12521 12521 12522 12522 12523 1252...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 50000 lines
Test #15:
score: 0
Accepted
time: 4467ms
memory: 24856kb
input:
50000 100000 100000 12500 12501 12501 12502 12502 12503 12503 12504 12504 12505 12505 12506 12506 12507 12507 12508 12508 12509 12509 12510 12510 12511 12511 12512 12512 12513 12513 12514 12514 12515 12515 12516 12516 12517 12517 12518 12518 12519 12519 12520 12520 12521 12521 12522 12522 12523 1252...
output:
NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES N...
result:
ok 50000 lines
Test #16:
score: 0
Accepted
time: 4474ms
memory: 24792kb
input:
50000 100000 100000 12500 12501 12501 12502 12502 12503 12503 12504 12504 12505 12505 12506 12506 12507 12507 12508 12508 12509 12509 12510 12510 12511 12511 12512 12512 12513 12513 12514 12514 12515 12515 12516 12516 12517 12517 12518 12518 12519 12519 12520 12520 12521 12521 12522 12522 12523 1252...
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 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 NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 50000 lines
Test #17:
score: 0
Accepted
time: 5616ms
memory: 23600kb
input:
50000 100000 100000 24500 24501 24501 24502 24502 24503 24503 24504 24504 24505 24505 24506 24506 24507 24507 24508 24508 24509 24509 24510 24510 24511 24511 24512 24512 24513 24513 24514 24514 24515 24515 24516 24516 24517 24517 24518 24518 24519 24519 24520 24520 24521 24521 24522 24522 24523 2452...
output:
NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES...
result:
ok 98000 lines
Test #18:
score: 0
Accepted
time: 5493ms
memory: 23812kb
input:
50000 100000 100000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 ...
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 100000 lines
Test #19:
score: 0
Accepted
time: 6230ms
memory: 19844kb
input:
50000 100000 100000 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98...
output:
NO YES YES YES NO NO YES YES YES NO YES YES NO YES YES NO YES NO NO NO NO NO YES YES NO YES NO YES YES YES NO NO YES NO NO NO YES YES YES YES NO YES NO NO YES YES YES NO NO YES YES YES YES NO YES YES NO NO YES YES NO NO YES NO NO NO YES NO NO NO YES NO NO NO YES NO YES NO NO YES YES NO NO YES NO NO ...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 6414ms
memory: 19364kb
input:
50000 100000 100000 3 6 6 9 9 12 12 15 15 18 18 21 21 24 24 27 27 30 30 33 33 36 36 39 39 42 42 45 45 48 48 51 51 54 54 57 57 60 60 63 63 66 66 69 69 72 72 75 75 78 78 81 81 84 84 87 87 90 90 93 93 96 96 99 99 102 102 105 105 108 108 111 111 114 114 117 117 120 120 123 123 126 126 129 129 132 132 13...
output:
YES NO NO NO YES NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO YES NO YES NO NO NO NO NO NO YES YES NO YES YES NO NO YES NO YES NO YES NO NO NO NO YES NO NO YES NO YES YES YES YES NO NO NO NO YES YES NO NO NO YES NO NO NO YES YES NO NO NO YES NO NO NO NO YES NO NO NO...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 50ms
memory: 17512kb
input:
5000 10000 10000 4103 3044 1509 4745 3287 2269 1227 1146 3580 1636 4103 1040 1747 4633 1572 1188 4212 2110 633 4726 1390 511 3571 20 3491 1138 332 4118 3445 1002 3848 4285 2373 4520 2276 2638 4003 4209 1647 3074 372 374 4317 202 3969 2571 1459 3606 2006 1859 1985 1755 4443 3420 449 3964 539 2829 347...
output:
NO YES NO NO YES NO YES YES NO NO YES YES YES YES NO NO YES YES YES YES YES NO YES NO NO YES YES YES NO YES YES NO NO YES NO NO NO NO NO YES YES NO NO YES YES YES YES YES YES NO NO YES NO NO YES YES NO YES NO YES YES NO NO NO YES YES NO YES YES YES YES NO NO NO NO YES YES YES YES NO YES NO YES YES Y...
result:
ok 5000 lines
Test #22:
score: 0
Accepted
time: 6560ms
memory: 75664kb
input:
50000 100000 100000 6061 22695 15954 27714 42835 31992 179 39077 21790 21794 12016 42264 25592 44016 9510 13155 41929 28310 27509 37593 27187 27022 41269 5119 3414 46640 17135 14546 33252 19903 32573 29689 15519 36864 31361 34103 41054 48474 1860 45033 46463 37990 35082 25907 22143 473 6195 19370 13...
output:
YES YES YES NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES NO NO YES YES NO YES YES YES YES YES NO YES YES NO NO YES YES NO YES YES NO NO NO YES NO YES YES NO NO YES NO YES NO YES NO YES YES YES YES YES NO NO YES YES YES NO YES YES NO YES YES NO YES YES YES NO Y...
result:
ok 50000 lines
Test #23:
score: 0
Accepted
time: 6483ms
memory: 78068kb
input:
50000 100000 100000 30380 30171 8714 21977 17910 23728 30792 35180 1097 6580 45454 42956 14954 6909 24599 12426 14136 36556 28901 29472 26695 24651 37956 14082 2515 31828 2289 29674 46083 46409 18706 29194 24371 229 31696 40513 48768 41897 27789 44824 10490 11482 6788 10306 15469 24437 14795 21470 4...
output:
YES NO NO YES YES YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES YES NO YES YES NO YES YES NO YES NO NO YES NO YES YES NO NO NO YES YES NO YES YES NO NO YES YES YES YES NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES NO NO NO NO NO YES YES YES NO YES NO NO Y...
result:
ok 50000 lines
Test #24:
score: 0
Accepted
time: 6701ms
memory: 18892kb
input:
50000 100000 100000 7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 77 77 84 84 91 91 98 98 105 105 112 112 119 119 126 126 133 133 140 140 147 147 154 154 161 161 168 168 175 175 182 182 189 189 196 196 203 203 210 210 217 217 224 224 231 231 238 238 245 245 252 252 259 259 266 266 273 273 ...
output:
NO NO YES NO NO YES YES NO YES NO NO YES YES YES YES YES YES YES NO YES NO NO YES YES NO NO YES YES YES NO NO YES YES NO YES NO NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO NO NO YES YES YES NO NO NO NO YES YES NO YES YES YES YES NO NO YES YES YES NO YES YES NO NO YES YES NO NO YES NO NO...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 6574ms
memory: 74392kb
input:
50000 100000 100000 233 466 466 699 699 932 932 1165 1165 1398 1398 1631 1631 1864 1864 2097 2097 2330 2330 2563 2563 2796 2796 3029 3029 3262 3262 3495 3495 3728 3728 3961 3961 4194 4194 4427 4427 4660 4660 4893 4893 5126 5126 5359 5359 5592 5592 5825 5825 6058 6058 6291 6291 6524 6524 6757 6757 69...
output:
YES NO NO YES YES YES NO NO NO YES YES YES YES YES NO NO YES YES YES NO YES YES YES YES YES YES YES YES NO NO NO YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES NO NO NO YES YES YES YES NO NO NO YES NO YES YES YES NO YES YES NO YES NO NO NO YES YES YES YES YES YES YES NO NO YES NO YES NO Y...
result:
ok 50000 lines
Test #26:
score: 0
Accepted
time: 6612ms
memory: 76580kb
input:
50000 100000 100000 13 26 26 39 39 52 52 65 65 78 78 91 91 104 104 117 117 130 130 143 143 156 156 169 169 182 182 195 195 208 208 221 221 234 234 247 247 260 260 273 273 286 286 299 299 312 312 325 325 338 338 351 351 364 364 377 377 390 390 403 403 416 416 429 429 442 442 455 455 468 468 481 481 4...
output:
YES YES YES NO YES NO YES NO NO YES NO YES YES NO YES NO YES YES YES NO YES NO YES YES YES YES NO NO NO NO YES YES NO NO NO YES YES YES YES YES YES YES NO YES YES NO YES YES NO YES NO YES NO YES YES YES YES NO NO YES YES YES YES YES NO NO YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YE...
result:
ok 50000 lines
Test #27:
score: 0
Accepted
time: 6434ms
memory: 75992kb
input:
50000 100000 100000 4 8 8 12 12 16 16 20 20 24 24 28 28 32 32 36 36 40 40 44 44 48 48 52 52 56 56 60 60 64 64 68 68 72 72 76 76 80 80 84 84 88 88 92 92 96 96 100 100 104 104 108 108 112 112 116 116 120 120 124 124 128 128 132 132 136 136 140 140 144 144 148 148 152 152 156 156 160 160 164 164 168 16...
output:
NO NO YES YES YES YES YES YES NO NO YES YES NO YES YES YES NO NO YES YES YES NO YES YES NO YES NO YES NO YES YES YES YES NO YES YES NO NO YES NO YES YES NO YES YES YES YES YES YES YES YES YES YES YES NO YES YES NO YES YES YES YES NO NO NO NO YES NO NO YES YES YES NO YES YES YES NO YES NO YES YES YES...
result:
ok 50000 lines
Test #28:
score: 0
Accepted
time: 6174ms
memory: 74524kb
input:
50000 100000 100000 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98...
output:
YES YES NO NO NO NO NO YES YES YES YES YES NO YES YES NO YES YES YES NO YES NO YES YES YES NO YES YES YES YES NO YES NO NO NO YES YES YES YES YES NO NO YES YES YES NO YES YES NO NO YES NO NO YES YES YES NO NO YES YES YES YES NO NO NO NO YES YES NO NO YES YES YES NO YES YES YES YES YES YES YES NO YES...
result:
ok 50000 lines
Test #29:
score: 0
Accepted
time: 5485ms
memory: 61884kb
input:
50000 100000 100000 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 ...
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 50000 lines
Test #30:
score: 0
Accepted
time: 5526ms
memory: 61192kb
input:
50000 100000 100000 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 ...
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 50000 lines
Test #31:
score: 0
Accepted
time: 5714ms
memory: 59972kb
input:
50000 100000 100000 2 1 3 2 4 3 5 4 6 5 1 6 8 7 9 8 10 9 11 10 12 11 7 12 14 13 15 14 16 15 17 16 18 17 13 18 20 19 21 20 22 21 23 22 24 23 19 24 26 25 27 26 28 27 29 28 30 29 25 30 32 31 33 32 34 33 35 34 36 35 31 36 38 37 39 38 40 39 41 40 42 41 37 42 44 43 45 44 46 45 47 46 48 47 43 48 50 49 51 5...
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 50000 lines
Test #32:
score: 0
Accepted
time: 883ms
memory: 18364kb
input:
22222 44442 99996 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
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 33333 lines