QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100151 | #185. Bridges | Bronya | 59 | 1940ms | 12668kb | C++20 | 2.6kb | 2023-04-24 20:24:14 | 2023-04-24 20:24:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,Q;
struct edge{
int u,v;
int a,b;
}e[200005];
int id[200005];
int ans[200005];
bool cmpp(int x,int y){
return (e[x].b<e[y].b);
}
struct bcj{
int siz;
}val[200005];
int fa[200005];
stack<pair<int,bcj>>rc;
int Find(int u){
return (fa[u]!=u?Find(fa[u]):u);
}
void merge(int u,int v){
u=Find(u),v=Find(v);
if(val[u].siz<val[v].siz)swap(u,v);
if(u!=v){
fa[v]=u;
rc.push(make_pair(v,val[u]));
}
else rc.push(make_pair(u,val[u]));
if(u!=v)val[u].siz+=val[v].siz;
}
void del(int u){
while(rc.size()>u){
int v=rc.top().first;
val[fa[v]]=rc.top().second;
fa[v]=v;
rc.pop();
}
}
set<pair<int,int> >hav;
vector<int>A;
vector<int>B;
int main(){
// freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].b);e[i].b=-e[i].b;
id[i]=i;
}
scanf("%d",&Q);
for(int i=1;i<=m;i++)e[i].a=m+Q;
for(int i=1;i<=Q;i++){
int opt;
scanf("%d",&opt);
if(opt==1){
int u;
scanf("%d",&u);
e[i+m]=e[id[u]];
e[id[u]].a=i+m-1;
scanf("%d",&e[i+m].b);e[i+m].b=-e[i+m].b;
id[u]=i+m;
}
else scanf("%d%d",&e[i+m].u,&e[i+m].b),e[i+m].a=-1,e[i+m].b=-e[i+m].b;
}
// for(int i=1;i<=m+Q;i++)cout<<e[i].a<<endl;
for(int i=1;i<=n;i++)fa[i]=i,val[i].siz=1;
int siz=sqrt(m+Q);
for(int i=1;(i-1)*siz+1<=m+Q;i++){
A.clear();B.clear();
for(auto j=hav.begin();j!=hav.end();j++){
int u=j->second;
if(e[u].a<min(i*siz,m+Q))A.push_back(u);
}
for(int j=0;j<A.size();j++)hav.erase(hav.find(make_pair(e[A[j]].b,A[j])));
for(int j=(i-1)*siz+1;j<=min(i*siz,m+Q);j++){
if(e[j].a==-1)B.push_back(j);
else A.push_back(j);
}
sort(B.begin(),B.end(),cmpp);
int L=0;
// cout<<L<<" "<<B.size()<<endl;
for(auto j=hav.begin();j!=hav.end();j++){
while(L<B.size()&&e[B[L]].b<j->first){
int now=rc.size();
for(int k=0;k<A.size();k++)
if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
merge(e[A[k]].u,e[A[k]].v);
int f1=Find(e[B[L]].u);
ans[B[L]]=val[f1].siz;
del(now);
L++;
}
// cout <<i <<" "<<j->second <<" "<<siz<<endl;
merge(e[j->second].u,e[j->second].v);
}
while(L<B.size()){
int now=rc.size();
for(int k=0;k<A.size();k++)
if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
merge(e[A[k]].u,e[A[k]].v);
int f1=Find(e[B[L]].u);
ans[B[L]]=val[f1].siz;
del(now);
L++;
}
del(0);
for(int j=0;j<A.size();j++){
if(e[A[j]].a<=i*siz)continue;
else hav.insert(make_pair(e[A[j]].b,A[j]));
}
}
for(int i=1;i<=m+Q;i++)
if(e[i].a==-1)printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 4ms
memory: 7788kb
input:
3 4 1 2 5 2 3 2 3 1 4 2 3 8 5 2 1 5 1 4 1 2 2 5 1 1 1 2 3 2
output:
3 2 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 7780kb
input:
7 8 1 2 5 1 6 5 2 3 5 2 7 5 3 4 5 4 5 5 5 6 5 6 7 5 12 2 1 6 1 1 1 2 1 2 1 2 3 2 2 2 1 5 2 1 3 1 2 2 4 2 4 2 1 8 1 2 1 1 2 1 3
output:
1 7 7 5 7 7 4
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 7824kb
input:
5 5 5 3 81 2 4 49 4 1 63 4 3 74 1 2 85 10 2 2 22 2 2 20 1 3 49 2 1 77 1 3 44 1 1 6 2 3 49 2 4 31 2 2 54 2 2 7
output:
5 5 2 4 4 2 4
result:
ok 7 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 5692kb
input:
5 10 1 3 51 1 2 74 2 4 63 1 4 86 2 5 9 5 1 28 5 4 1 2 1 23 2 5 16 3 1 75 10 2 2 37 1 6 24 1 1 24 2 5 65 1 7 57 2 1 82 2 1 26 1 4 12 2 2 15 1 4 70
output:
4 1 2 5 5
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 16ms
memory: 5788kb
input:
100 1000 26 42 977322268 4 29 374382133 1 19 717262653 80 56 835233390 58 54 591443635 63 6 579687470 85 81 118110131 33 100 533388119 24 46 591205239 94 32 637495476 60 93 638216409 55 7 413175730 38 43 414269997 48 30 773236579 67 27 441100383 44 36 784705206 28 56 300064078 13 60 490548719 94 19 ...
output:
100 100 100 100 100 100 100 100 17 100 100 100 100 100 5 100 98 100 100 100 100 100 100 100 100 100 100 100 100 96 100 2 42 100 100 100 86 97 100 100 100 98 100 100 100 100 100 97 100 100 100 100 100 100 100 100 100 100 100 100 100 98 100 100 100 100 100 5 100 100 100 100 100 98 100 100 100 100 1 10...
result:
ok 4938 lines
Test #6:
score: 0
Accepted
time: 2ms
memory: 5756kb
input:
1 0 10000 2 1 198824732 2 1 485321921 2 1 632483476 2 1 51814372 2 1 599796663 2 1 786502474 2 1 231528808 2 1 911511073 2 1 372581312 2 1 168699670 2 1 155928174 2 1 636544973 2 1 221309003 2 1 934838177 2 1 927074369 2 1 66460573 2 1 854380894 2 1 763039163 2 1 203254324 2 1 525763932 2 1 58538356...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 11ms
memory: 7732kb
input:
14 91 14 9 741787656 13 11 380113631 4 1 156765724 5 10 110432834 3 2 1 5 8 39463185 6 7 725978322 13 4 785136504 8 11 446396092 2 1 949863738 10 9 808326751 3 14 623625192 13 1 73346434 4 3 319943247 10 11 874189144 6 5 177923890 14 11 892698206 10 8 602358072 10 12 7684455 14 8 228264999 12 2 8612...
output:
14 14 14 14 1 2 10 14 14 14 1 14 10 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 12 14 1 14 14 14 14 1 14 2 14 14 14 14 14 14 14 14 14 14 13 14 14 14 14 14 14 14 1 14 14 14 2 14 14 14 14 14 14 14 3 14 14 14 14 14 14 14 1 14 14 2 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 14 14 14 1 14...
result:
ok 5047 lines
Test #8:
score: 0
Accepted
time: 7ms
memory: 7768kb
input:
14 91 14 9 811041661 13 11 347161250 4 1 1000000000 5 10 1000000000 3 2 190616738 5 8 1000000000 6 7 1000000000 13 4 839799889 8 11 1000000000 2 1 1000000000 10 9 925475672 3 14 327778434 13 1 709412306 4 3 696232213 10 11 1000000000 6 5 1000000000 14 11 994412543 10 8 1000000000 10 12 1000000000 14...
output:
10 10 10 10 10 10 14 10 10 14 14 10 10 14 10 14 14 10 10 10 10 10 14 14 13 10 10 10 10 10 14 10 10 10 10 10 10 14 10 10 10 14 10 10 10 10 10 10 10 10 14 10 10 14 10 1 10 13 14 14 14 10 10 10 10 10 10 10 10 10 14 10 10 10 10 14 10 10 10 10 10 10 10 10 10 10 14 10 10 10 10 10 10 14 14 14 10 10 14 14 1...
result:
ok 5085 lines
Test #9:
score: 0
Accepted
time: 9ms
memory: 5724kb
input:
100 100 74 34 685914765 44 9 1 41 36 6 49 22 1 40 84 1 7 40 1 57 31 264482875 16 87 3 66 10 3 68 7 2 92 43 2 33 57 736695588 42 23 2 64 45 1 85 81 4 43 84 1 62 91 2 13 49 2 95 50 1 76 54 1 49 88 1 37 73 2 48 60 1 65 85 3 69 62 2 60 26 1 15 12 1 82 51 2 100 25 3 21 78 1 59 52 1 10 49 2 80 60 2 89 8 3...
output:
84 15 84 84 84 84 84 84 1 84 5 1 84 3 3 1 1 1 1 84 10 84 7 1 84 1 84 1 1 4 84 3 19 1 15 84 84 84 1 84 84 84 84 2 1 84 4 1 2 84 1 84 84 84 2 2 84 84 1 2 84 3 1 5 1 1 4 1 1 84 84 3 20 84 4 6 84 9 4 1 84 1 1 1 84 84 84 84 84 1 84 21 5 2 2 1 1 84 4 84 84 84 5 1 4 6 84 21 1 21 84 84 84 2 84 1 1 1 84 1 84...
result:
ok 4993 lines
Test #10:
score: 0
Accepted
time: 8ms
memory: 7760kb
input:
100 100 74 34 1000000000 44 9 715200993 41 36 904630372 49 22 962500864 40 84 729454076 7 40 377495011 57 31 1000000000 16 87 325040395 66 10 52188391 68 7 212790030 92 43 78499164 33 57 1000000000 42 23 501453286 64 45 269034829 85 81 219465148 43 84 451775169 62 91 579206993 13 49 553447314 95 50 ...
output:
1 60 5 2 24 22 2 1 1 4 40 1 77 72 1 4 1 38 1 2 42 1 3 1 76 1 1 1 2 51 1 28 74 1 38 80 76 1 1 69 3 83 1 5 5 5 83 68 5 2 1 1 1 81 5 2 1 4 1 2 5 52 1 5 78 1 51 2 5 71 2 66 1 84 2 36 1 8 3 1 1 1 78 1 68 81 16 76 2 84 84 2 5 1 63 2 1 63 1 1 74 76 5 1 5 3 1 1 1 1 3 1 1 3 2 5 1 2 24 5 1 1 21 1 1 81 21 4 3 ...
result:
ok 4993 lines
Test #11:
score: 0
Accepted
time: 10ms
memory: 7788kb
input:
100 100 74 34 228801803 44 9 1 41 36 4 49 22 1 40 84 4 7 40 3 57 31 704030998 16 87 4 66 10 1 68 7 7 92 43 1 33 57 728028523 42 23 1 64 45 3 85 81 4 43 84 3 62 91 3 13 49 1 95 50 1 76 54 1 49 88 1 37 73 3 48 60 4 65 85 1 69 62 1 60 26 4 15 12 3 82 51 4 100 25 1 21 78 4 59 52 3 10 49 1 80 60 2 89 8 6...
output:
5 84 84 84 84 84 1 84 84 84 84 84 1 84 84 84 84 1 84 84 1 1 84 1 84 1 84 84 84 84 84 84 84 84 84 84 84 84 84 84 1 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 1 84 84 84 1 84 84 84 1 84 84 84 84 84 84 84 84 84 1 84 84 84 84 5 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84...
result:
ok 4976 lines
Test #12:
score: 0
Accepted
time: 8ms
memory: 7792kb
input:
100 100 75 55 18370417 87 15 24759751 35 90 180232308 93 13 4822137 52 63 94962544 47 83 518290304 79 21 1829303 7 97 537385812 75 19 52188390 25 8 212790030 87 43 24037796 44 94 324191076 9 92 333255997 54 51 12968272 34 6 253267674 95 64 20519430 31 58 28891962 12 23 575634244 50 4 110619991 33 9 ...
output:
3 1 82 100 1 2 100 1 1 1 2 22 6 3 10 3 16 10 22 2 1 1 4 1 2 8 3 5 7 1 32 1 6 12 8 2 6 3 6 3 1 55 100 1 4 2 5 4 1 1 2 13 75 3 1 55 6 2 3 1 9 1 13 1 9 60 3 1 1 100 1 1 1 100 15 1 3 3 75 6 100 12 15 1 2 3 8 1 8 15 6 1 3 1 1 14 4 1 1 3 8 2 1 12 24 4 2 1 30 3 100 1 1 1 4 24 1 6 1 1 15 4 30 1 13 1 3 1 3 7...
result:
ok 4993 lines
Test #13:
score: 0
Accepted
time: 5ms
memory: 7740kb
input:
100 100 75 55 827381885 87 15 189426033 35 90 314088225 93 13 962500864 52 63 771307313 47 83 930460632 79 21 691878465 7 97 859582759 75 19 557403081 25 8 989321957 87 43 217067250 44 94 805985038 9 92 924454229 54 51 269034829 34 6 811380927 95 64 180328209 31 58 436656654 12 23 947277637 50 4 917...
output:
5 8 1 7 1 7 6 48 11 3 1 13 2 5 1 60 1 1 13 1 2 45 2 1 2 1 5 13 1 4 3 1 4 52 52 4 31 1 52 4 1 1 2 1 2 1 2 1 3 24 60 2 8 1 14 2 1 2 3 2 7 1 8 4 8 2 100 2 4 19 2 1 8 100 1 4 2 90 17 1 2 48 2 48 1 3 4 3 17 1 3 2 2 2 3 1 4 2 1 1 1 3 1 44 3 5 1 90 1 16 5 14 1 3 2 1 5 63 3 5 1 3 1 42 2 14 5 1 1 1 2 1 4 1 3...
result:
ok 4993 lines
Test #14:
score: 0
Accepted
time: 11ms
memory: 7792kb
input:
100 100 75 55 523280580 87 15 97273903 35 90 24566276 93 13 66762694 52 63 62457076 47 83 14559451 79 21 198058038 7 97 303933384 75 19 357282957 25 8 15676722 87 43 20498361 44 94 361533141 9 92 479521475 54 51 188367392 34 6 351945785 95 64 31785315 31 58 12985500 12 23 63507527 50 4 25758008 33 9...
output:
1 1 5 13 9 1 11 4 7 25 2 13 15 1 13 66 33 3 13 5 1 2 1 1 4 11 13 9 4 1 3 9 16 7 11 1 7 11 28 5 11 13 9 9 13 2 5 10 9 15 4 24 3 3 9 62 15 3 9 1 14 17 1 13 1 17 9 4 1 1 15 11 2 9 9 1 10 4 1 3 9 2 13 1 4 9 9 5 65 1 62 13 13 11 11 1 6 1 1 1 6 8 99 7 3 1 3 1 5 32 1 1 9 3 18 6 4 65 10 66 1 9 3 2 4 10 4 65...
result:
ok 4952 lines
Test #15:
score: 0
Accepted
time: 12ms
memory: 7776kb
input:
100 150 72 39 459437566 99 33 240975967 60 42 71297038 100 66 81817608 7 97 40586687 94 44 488433191 9 33 155257410 38 59 258106533 34 6 7722722 97 89 212790030 73 34 78499164 83 88 261128013 39 98 335913783 20 81 140652810 14 30 129337570 83 47 56555466 18 2 676617230 37 42 79132016 80 35 633142513...
output:
1 1 11 1 1 3 6 41 4 1 25 2 5 5 2 46 45 2 23 34 34 26 11 26 1 6 23 1 100 5 100 2 1 5 30 6 4 61 62 26 5 26 100 26 100 2 1 5 3 1 66 27 26 26 100 3 26 16 24 26 26 18 1 7 1 3 34 67 1 7 5 30 100 4 3 18 27 18 1 3 3 71 19 66 7 24 39 9 26 98 39 100 1 42 38 5 11 100 42 26 1 37 1 27 100 40 42 37 5 37 37 58 40 ...
result:
ok 5046 lines
Test #16:
score: 0
Accepted
time: 5ms
memory: 5736kb
input:
100 150 72 39 950686765 99 33 716054509 60 42 836724016 100 66 497108440 7 97 168321467 94 44 992895576 9 33 938438676 38 59 548639568 34 6 773535187 97 89 982737825 73 34 894334764 83 88 687830748 39 98 950242721 20 81 613284326 14 30 602412784 83 47 673179224 18 2 917339878 37 42 581986238 80 35 9...
output:
1 4 3 3 22 1 2 22 2 3 1 4 20 1 1 58 22 30 3 1 2 1 8 1 16 4 3 22 1 46 2 2 16 3 1 1 14 5 1 1 8 2 1 1 100 5 16 1 1 6 3 1 1 1 100 4 100 14 27 45 1 2 1 10 1 4 31 100 1 3 1 1 2 1 1 1 17 2 50 24 2 1 40 54 1 2 2 4 4 1 1 1 4 31 1 1 1 1 4 100 8 11 7 22 2 2 16 1 4 1 2 1 4 1 13 5 18 1 99 1 10 25 100 1 10 3 18 9...
result:
ok 5046 lines
Test #17:
score: 0
Accepted
time: 12ms
memory: 5768kb
input:
100 150 72 39 23280580 99 33 97273903 60 42 24566276 100 66 254262694 7 97 437457076 94 44 139559451 9 33 10558038 38 59 241433384 34 6 107282957 97 89 140676722 73 34 20498361 83 88 111533141 39 98 604521475 20 81 188367392 14 30 226945785 83 47 94285315 18 2 512985500 37 42 313507527 80 35 1507580...
output:
61 1 22 3 18 14 19 1 19 5 1 1 37 1 100 30 72 18 98 99 1 1 1 100 3 30 17 23 18 1 18 18 1 100 2 8 2 30 18 8 29 1 1 45 100 1 28 1 24 6 1 1 100 1 2 15 1 69 9 30 1 17 29 69 1 99 20 11 99 99 6 1 6 29 1 23 99 11 1 29 9 3 3 1 18 22 22 42 4 28 29 1 2 1 98 3 29 1 1 29 18 99 1 19 1 41 29 8 97 1 16 8 68 3 8 8 1...
result:
ok 5078 lines
Test #18:
score: 0
Accepted
time: 6ms
memory: 5724kb
input:
100 100 92 90 2 13 45 2 64 25 1 56 84 1 65 57 1 95 8 1 69 40 2 19 62 1 93 82 1 69 86 1 13 95 2 32 36 1 30 69 2 28 85 2 61 19 2 16 95 1 18 75 2 99 24 2 75 54 2 94 17 1 5 4 1 77 43 2 46 97 2 20 2 1 61 53 2 92 73 1 27 43 1 10 41 1 39 13 2 58 37 1 57 70 1 4 18 1 14 69 1 75 52 2 38 50 1 50 97 1 81 10 2 1...
output:
10 2 1 80 2 80 3 1 3 80 80 80 80 3 2 1 80 1 80 80 1 4 80 80 12 80 12 80 1 80 3 12 12 80 80 80 1 2 80 80 4 1 80 1 1 1 2 80 1 80 2 1 1 1 17 1 1 80 80 3 1 80 1 80 80 80 1 1 5 80 11 2 80 80 80 1 2 80 1 1 2 4 80 1 2 11 4 80 18 80 18 1 4 80 1 2 80 80 1 80 80 6 80 1 1 6 7 2 6 16 80 4 80 1 2 1 2 80 1 80 16 ...
result:
ok 4949 lines
Test #19:
score: 0
Accepted
time: 9ms
memory: 5720kb
input:
100 100 20 34 3 91 98 2 40 13 1 34 24 1 55 90 3 12 23 1 87 80 3 96 71 1 50 98 2 26 3 1 32 66 1 64 45 3 60 44 3 42 77 3 54 78 2 99 2 2 36 46 1 51 10 2 67 96 2 15 60 1 8 25 3 51 78 1 19 20 3 54 59 3 72 68 1 22 29 1 80 51 2 54 68 1 70 77 1 9 91 2 41 64 2 17 22 3 5 91 2 58 39 1 66 15 2 8 6 3 66 80 3 71 ...
output:
10 1 5 81 81 4 52 1 81 1 1 1 81 2 1 50 1 57 1 2 1 2 81 1 5 1 16 16 3 1 1 1 2 2 81 81 3 1 81 2 1 2 81 4 1 81 3 1 1 81 81 30 2 81 30 81 1 81 30 1 1 81 81 3 2 1 32 4 1 1 1 1 81 81 3 1 4 2 1 81 1 48 6 4 1 81 81 1 81 1 4 81 1 81 6 1 1 3 81 1 52 81 1 52 81 5 81 81 1 81 6 5 2 81 1 2 1 9 4 1 1 81 1 1 4 40 1...
result:
ok 5065 lines
Subtask #2:
score: 16
Accepted
Test #20:
score: 16
Accepted
time: 1738ms
memory: 11256kb
input:
50000 49999 1 2 976392398 2 3 773336157 3 4 849545817 4 5 194340376 5 6 386778507 6 7 40561907 7 8 260116638 8 9 85673124 9 10 149683208 10 11 724746156 11 12 155084527 12 13 416939763 13 14 753621724 14 15 384948880 15 16 625917615 16 17 833747431 17 18 764302034 18 19 4518648 19 20 405679793 20 21...
output:
7 2 24 1 3 8 1 2 6 2 535 4 3 2 7 13 40 110 3 41 6 1 108 491 28 1 1 4 2 11 5 9 2 1 2 1 9 1 1 3 1 14 3 1 1 10 44 3 2 3 3 1 1 18 3 2 2 2 1 9 1 15 17 7 1 1 1 4 1 2 6 3 1 1 5 1 10 1 5 2 1 14 14 3 28 17 1 6 1 3 1 9 3 10 2 32 54 4 1 2 2 18 1 1 5 1 11 2 10 1 2 5 4 1 1 2 3 4 1 1 128 17 3 1 2 2 1 160 1 1 2 3 ...
result:
ok 49863 lines
Test #21:
score: 0
Accepted
time: 1752ms
memory: 11272kb
input:
50000 49999 1 2 491 2 3 15360 3 4 24312 4 5 17754 5 6 40601 6 7 30620 7 8 69533 8 9 144923 9 10 304551 10 11 264913 11 12 265173 12 13 135700 13 14 61571 14 15 6841 15 16 413217 16 17 596083 17 18 157633 18 19 68400 19 20 348725 20 21 494086 21 22 327898 22 23 569190 23 24 195301 24 25 402492 25 26 ...
output:
6 7 16 2 13 24 24 8 1 3 5 257 1 3 6 1 112 2 5 2 11 1 6 2 6 1 1 4 177 7 19 1 1 42 10 2 25 4 24 4 1 3 3 2 1 1 5 1 3 2 13 1 1 1 2 3 5 3 9 2 16 4 10 6 7 3 1 2 17 37 3 1 4 1 4 1 3 7 1 2 2 1 135 3 34 5 2 2 8 2 1 1 1 1 4 3 1 3 2 5 2 1 5 1 2 5 503 3 1 9 7 1 2 4 2 3 5 9 2 15 3 7 9 16 1 28 5 2 5 4 2 3 8 9 4 1...
result:
ok 49979 lines
Test #22:
score: 0
Accepted
time: 1727ms
memory: 11172kb
input:
50000 49999 1 2 20928 2 3 33937 3 4 35582 4 5 123172 5 6 100214 6 7 105156 7 8 46684 8 9 124995 9 10 13728 10 11 209960 11 12 206098 12 13 146953 13 14 370445 14 15 141005 15 16 536276 16 17 80350 17 18 258276 18 19 401626 19 20 32874 20 21 125207 21 22 357075 22 23 598244 23 24 46414 24 25 609917 2...
output:
3 1 1 1 2 1 2 10 7 1 43 3 6 1 4 1 8 1 82 5 3 1 1 2 1 11 5 45 21 1 1 10 2 5 8 2 1 12 1 29 2 1 4 5 2 56 3 3 3 14 1 1 29 9 160 4 3 5 2 2 1 2 6 3 2 11 2 8 1 8 3 3 9 199 1 1 1 1 1 1 1 11 23 2 2 9 339 2 2 1 2 3 1 1 116 6 5 5 10 3 1 1 2 1 18 1 1 6 1 1 8 3 3 1 1 24 1 1 3 1 1 5 12 10 1 6 1 3 2 4 1 2 1 5 6 1 ...
result:
ok 50005 lines
Test #23:
score: 0
Accepted
time: 1781ms
memory: 11364kb
input:
50000 49999 1 2 111167988 2 3 402479521 3 4 873342766 4 5 303335487 5 6 357259867 6 7 944570848 7 8 227864068 8 9 137899415 9 10 782881158 10 11 545137901 11 12 125756079 12 13 713912399 13 14 516355545 14 15 306731193 15 16 244028251 16 17 175980262 17 18 956260270 18 19 92690286 19 20 344996907 20...
output:
1 8 1 1 1 1 6 11 21 12 5 3 105 1 1 2 4 5 1 16 1 2 1 3 1 3 2 1 1 2 1 30 2 29 9 8 6 16 1 24 5 8 2 1 5 33 10 12 5 28 10 2 1 1 6 1 2 1 1 1 1 17 7 12 2 3 10 6 2 89 38 2 2 1 2 5 6 1 1 107 47 1 1 1 1 9 1 1 13 2 12 6 1 1 9 9 2 16 1 2 2 2 15 1 4 5 5 1 1 116 5 1 7 5 3 18 1 1 1 14 1 2 1 1 1 3185 1 3 3 2 1 3 7 ...
result:
ok 49979 lines
Test #24:
score: 0
Accepted
time: 1773ms
memory: 10984kb
input:
50000 49999 1 2 993457878 2 3 126364173 3 4 200415238 4 5 739704607 5 6 676532686 6 7 557507714 7 8 71727068 8 9 337809709 9 10 681106495 10 11 599345798 11 12 346312387 12 13 39200895 13 14 943426213 14 15 506779546 15 16 379338416 16 17 14615880 17 18 816406736 18 19 211045210 19 20 838922528 20 2...
output:
5 9 18 53 19 1 25 4 19 1 1 1 1 1 11 1 1 2 1 9 1 13 16 5 1 2 1 1 1 7 1 1 16 1 1 5 3 2 3 3 11 2 1 1 12 1 16987 4 12 1 1 1 5 5 5 1 1 4 1 4 2 1 3 1 4 1 1 2 5 2 18 1 3 200 1 4 2 7 1 1 1 2 44 2 1 10 11 2 3 12 1 3 4 10 4 7 1 16 6 1 13 4 1 5 3 2 1 2 2 2 1 31 40 3 2 1 3 1 86 2 2 1 1 1 1 15 2 1 1 1 6 1 1 7 1 ...
result:
ok 50005 lines
Test #25:
score: 0
Accepted
time: 1878ms
memory: 11196kb
input:
50000 49999 1 2 2180 2 3 39922 3 4 2857 4 5 41405 5 6 71574 6 7 34628 7 8 271216 8 9 134571 9 10 77206 10 11 98084 11 12 86039 12 13 449514 13 14 490107 14 15 450572 15 16 139688 16 17 639236 17 18 247981 18 19 75121 19 20 300881 20 21 7682 21 22 248842 22 23 599408 23 24 647942 24 25 7276 25 26 470...
output:
49496 49499 49314 30098 32346 32346 49499 30098 42345 4779 49496 42345 49314 32346 49496 49314 30098 1640 30098 30098 30098 6969 6968 40954 49314 30098 2248 30098 30098 403 40954 6969 49314 6969 30098 49498 30098 4779 40954 49499 6968 42345 30098 32346 1345 32346 49314 32346 40954 32346 6969 6969 33...
result:
ok 49911 lines
Test #26:
score: 0
Accepted
time: 1925ms
memory: 11136kb
input:
49999 49998 1 2 2541 2 3 57948 3 4 37666 4 5 66268 5 6 42284 6 7 115405 7 8 248366 8 9 262167 9 10 145846 10 11 47627 11 12 431021 12 13 218051 13 14 401077 14 15 549059 15 16 169347 16 17 363982 17 18 490171 18 19 370535 19 20 480055 20 21 327730 21 22 278018 22 23 231965 23 24 256156 24 25 329573 ...
output:
450 33828 47494 47494 1249 47493 9064 9064 24764 8175 47493 8175 33828 19203 19203 3968 1811 8175 5561 1689 42003 8175 33828 42003 33828 47494 19203 5561 24764 47494 3968 16782 24764 19203 24764 47494 24764 8175 24764 47493 9064 75 9064 1689 47494 1689 1689 24764 5561 2976 33828 3968 33828 78 24764 ...
result:
ok 50105 lines
Test #27:
score: 0
Accepted
time: 1940ms
memory: 11260kb
input:
49999 49998 1 2 23701 2 3 57539 3 4 70283 4 5 136271 5 6 141212 6 7 184696 7 8 228429 8 9 29895 9 10 31218 10 11 282781 11 12 29995 12 13 131524 13 14 133988 14 15 197273 15 16 351724 16 17 391575 17 18 253620 18 19 611546 19 20 216997 20 21 305541 21 22 118275 22 23 306021 23 24 482979 24 25 709132...
output:
26373 8528 1944 10472 1430 6356 3806 5934 1944 49998 8528 11437 369 363 36932 4327 3351 3351 3806 6496 1944 49973 5934 13041 19188 1857 652 2143 13254 13254 12975 49998 599 8528 1944 10472 5934 8528 19 10472 13254 10472 1935 4327 6356 11339 36932 13254 10472 4257 3806 610 6496 5934 2220 11437 1300 4...
result:
ok 50026 lines
Test #28:
score: 0
Accepted
time: 28ms
memory: 8120kb
input:
1 0 100000 2 1 710454586 2 1 30174257 2 1 685675008 2 1 417816804 2 1 327755609 2 1 841371333 2 1 301370841 2 1 143821498 2 1 232099091 2 1 977178764 2 1 572665966 2 1 913418066 2 1 808399404 2 1 22331931 2 1 434460344 2 1 40437984 2 1 997406768 2 1 40071081 2 1 268638772 2 1 541398526 2 1 983507437...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 1306ms
memory: 11276kb
input:
50000 49999 1 2 2 2 3 2 3 4 1 4 5 2 5 6 2 6 7 1 7 8 1 8 9 2 9 10 2 10 11 1 11 12 1 12 13 2 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 2 19 20 2 20 21 1 21 22 2 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 2 28 29 2 29 30 2 30 31 2 31 32 1 32 33 1 33 34 2 34 35 2 35 36 2 36 37 2 37 38 2 38 39 1 3...
output:
50000 50000 50000 50000 6 2 2 50000 50000 50000 50000 50000 50000 6 50000 1 1 50000 50000 4 4 50000 1 50000 50000 3 50000 2 50000 2 3 50000 1 50000 4 50000 50000 4 50000 50000 5 50000 9 50000 50000 10 3 5 50000 1 50000 50000 50000 50000 1 50000 50000 50000 3 50000 2 3 1 50000 50000 50000 50000 3 500...
result:
ok 49970 lines
Test #30:
score: 0
Accepted
time: 1376ms
memory: 10892kb
input:
50000 49999 1 2 2 2 3 2 3 4 2 4 5 2 5 6 1 6 7 3 7 8 1 8 9 3 9 10 3 10 11 1 11 12 3 12 13 2 13 14 2 14 15 2 15 16 3 16 17 3 17 18 3 18 19 1 19 20 2 20 21 3 21 22 1 22 23 2 23 24 1 24 25 3 25 26 3 26 27 3 27 28 3 28 29 3 29 30 3 30 31 1 31 32 3 32 33 1 33 34 2 34 35 2 35 36 2 36 37 1 37 38 3 38 39 1 3...
output:
50000 1 1 50000 50000 1 50000 50000 1 3 1 2 6 50000 50000 50000 50000 2 2 4 2 50000 5 3 50000 8 1 1 3 2 50000 50000 2 9 1 50000 50000 5 50000 1 7 50000 50000 6 1 9 5 4 4 1 3 50000 1 50000 3 2 2 50000 2 50000 4 5 50000 1 4 50000 5 50000 7 3 3 6 2 50000 3 12 50000 2 2 50000 9 50000 5 50000 50000 50000...
result:
ok 50021 lines
Test #31:
score: 0
Accepted
time: 1572ms
memory: 11292kb
input:
49999 49998 1 2 17203 2 3 2847 3 4 78198 4 5 153265 5 6 167348 6 7 223540 7 8 247201 8 9 165110 9 10 39406 10 11 169131 11 12 77633 12 13 189498 13 14 426647 14 15 370032 15 16 150693 16 17 137818 17 18 532098 18 19 516136 19 20 378632 20 21 155025 21 22 514837 22 23 297354 23 24 420776 24 25 391135...
output:
16669 3311 16669 16669 27851 626 13228 12829 2938 43909 399 2604 27851 10120 442 16669 13228 3783 3311 12829 16669 4348 27851 673 3311 624 12829 208 4348 4398 16669 2830 16669 16669 16669 16669 16669 10120 16669 1063 1424 13228 16669 16669 624 1424 2604 16669 16669 12829 12829 10120 12829 21017 2107...
result:
ok 89927 lines
Test #32:
score: 0
Accepted
time: 1693ms
memory: 11040kb
input:
49999 49998 1 2 15625 2 3 58909 3 4 79176 4 5 78230 5 6 108291 6 7 91661 7 8 34888 8 9 86333 9 10 196105 10 11 339006 11 12 66021 12 13 415608 13 14 107020 14 15 197675 15 16 190986 16 17 61241 17 18 430747 18 19 10073 19 20 696099 20 21 681217 21 22 687623 22 23 216763 23 24 8263 24 25 341165 25 26...
output:
208 53 4539 359 704 2952 7275 15294 1317 8926 49868 9467 10243 49868 9467 8926 4254 1224 2952 1463 4254 9467 10243 4539 9467 7275 29898 10243 9467 11529 2253 9467 7275 29898 9467 29898 9467 7275 4254 9467 40141 1127 45624 47145 519 1288 4254 40141 2952 49999 7275 29898 2952 10243 7275 40141 640 6918...
result:
ok 9962 lines
Subtask #3:
score: 17
Accepted
Test #33:
score: 17
Accepted
time: 1094ms
memory: 9844kb
input:
32767 32766 1 2 152523690 1 3 736211233 2 4 163158345 2 5 200010458 3 6 902682843 3 7 427399287 4 8 770411775 4 9 322256303 5 10 252775416 5 11 346597970 6 12 297314023 6 13 727299741 7 14 985621564 7 15 101953231 8 16 405434218 8 17 421655547 9 18 817411034 9 19 310455840 10 20 355126049 10 21 7038...
output:
1 1 2 2 6 6 12547 1 1 1793 3 41 1 37 29734 8197 1 1 1 2 11 3 7 5 18 39 13 136 1 2 1 1 4 2 177 3 279 2 36 114 53 4 9 3 2 1 21 6 2 2 5 2 1 6 7 1 5 4 11 23129 288 196 8 1 5 9 3 1 4 45 4 1 1 5 3 3 10 18 91 1 16 829 24 1 2 8 1247 10 2 1 7 20323 8 1 2 28551 1 6 1 12 4 3 1 27 1 1 1 1 2 3 1 7 1 487 1 21 15 ...
result:
ok 50019 lines
Test #34:
score: 0
Accepted
time: 334ms
memory: 8620kb
input:
8191 8190 1 2 217141764 1 3 529497259 2 4 779147272 2 5 691696039 3 6 48118037 3 7 603814603 4 8 696908741 4 9 217271102 5 10 68704258 5 11 22697519 6 12 683544026 6 13 723792342 7 14 793130995 7 15 92576446 8 16 327755609 8 17 103625834 9 18 543827967 9 19 341371333 10 20 640187172 10 21 85328878 1...
output:
3231 8191 580 3382 8191 8191 8191 8191 3212 6 4 7 6 3187 6120 6152 4 457 8191 7 2 8191 8191 8191 8191 8191 4 8191 8191 8191 8191 3605 8191 7 8191 5715 6975 8191 8191 4289 2 8191 6977 8191 2 8191 8191 4 1 1 8191 1 8191 8191 11 8191 8191 222 1 8191 5905 8191 8191 8060 8191 8191 8191 2 1 8191 8191 8191...
result:
ok 49969 lines
Test #35:
score: 0
Accepted
time: 1104ms
memory: 10476kb
input:
32767 32766 1 2 217141764 1 3 529497259 2 4 762168910 2 5 862501617 3 6 287569355 3 7 60434037 4 8 741381891 4 9 846044727 5 10 559556243 5 11 841922729 6 12 260807264 6 13 108798675 7 14 165384865 7 15 803171234 8 16 680929744 8 17 534495504 9 18 618761142 9 19 633256718 10 20 244069182 10 21 40934...
output:
32767 32767 32767 32767 32767 32767 32767 32767 32767 32767 3 32767 16965 32767 2 26 32767 32767 6 1 32767 7826 32767 1 21971 7 32767 12668 5289 162 32767 15263 32767 11 32767 3 4 32767 18 118 32767 1 32767 32767 32767 5 32767 32767 39 32767 267 32767 32767 32767 32767 32767 1 7 32767 2 32767 1 228 ...
result:
ok 50058 lines
Test #36:
score: 0
Accepted
time: 1107ms
memory: 10000kb
input:
32767 32766 1 2 960028533 1 3 932018255 2 4 966739858 2 5 978817181 3 6 951511415 3 7 993940257 4 8 988418327 4 9 995978961 5 10 810804356 5 11 990996089 6 12 988830283 6 13 964972868 7 14 860937540 7 15 840655680 8 16 840257957 8 17 761892560 9 18 901480224 9 19 889396012 10 20 884899819 10 21 9367...
output:
5 1 6 19293 1 17937 1 1 1 1 1 3 7 1 4 6883 32026 1 1 1 2 5824 2 19 2 28839 7 1 8 12099 19229 27469 2 3 1 10692 1 21275 1 2 1 31 1 1 1 15551 1 1 1 32498 7 31105 29865 1870 31927 1 3 1 1 1 1 27524 1 9 29426 4 1 12 4 26271 1 18126 2 1 1 1 1 31028 6 8 14285 1 3103 3 2 8 2 31181 1 1 1 21314 1 7 2 1 1 244...
result:
ok 50058 lines
Test #37:
score: 0
Accepted
time: 33ms
memory: 7740kb
input:
1 0 100000 2 1 710454586 2 1 30174257 2 1 685675008 2 1 417816804 2 1 327755609 2 1 841371333 2 1 301370841 2 1 143821498 2 1 232099091 2 1 977178764 2 1 572665966 2 1 913418066 2 1 808399404 2 1 22331931 2 1 434460344 2 1 40437984 2 1 997406768 2 1 40071081 2 1 268638772 2 1 541398526 2 1 983507437...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #38:
score: 0
Accepted
time: 1128ms
memory: 9764kb
input:
32767 32766 1 2 304863256 1 3 602102863 2 4 381894905 2 5 32190927 3 6 257274874 3 7 843197505 4 8 480275676 4 9 93549775 5 10 363411747 5 11 765890415 6 12 610483185 6 13 451529600 7 14 654899236 7 15 24173250 8 16 387501501 8 17 763650861 9 18 561615412 9 19 651242897 10 20 715964996 10 21 1542732...
output:
930 34 28341 6 1 2273 3373 19210 1 1 301 1 3410 1 1 1 24965 24019 1 5974 59 1 1 1 1 22 4307 12766 1192 17423 12976 6 1 29017 1 1 11 5 12750 5 21457 101 16242 4 1 47 17642 5 63 6 26577 46 22993 1 2 114 20 31591 31858 3 1 30277 1 29617 48 1 1 18339 536 3 21832 22066 4364 1 2 17629 1167 1475 7 39 1 542...
result:
ok 50054 lines
Test #39:
score: 0
Accepted
time: 1086ms
memory: 9804kb
input:
32767 32766 1 2 482946680 1 3 880684411 2 4 486062030 2 5 753631684 3 6 451749132 3 7 539244314 4 8 295789966 4 9 353762227 5 10 461289276 5 11 473918705 6 12 516181394 6 13 29129197 7 14 223169542 7 15 734712283 8 16 7164799 8 17 100959247 9 18 777798154 9 19 145416338 10 20 51605940 10 21 47461960...
output:
24646 1 1 1 27208 1 1 1 1 1 18717 1 1 1 1 48 1 1 2 2 1032 1 1 43 1 1 2 1 3 3 1 1 1 2 1 1 1 1 1 3 1 6 89 1 1 2 1 1 1 8000 1 1 1 1 1 31 1 1 738 1 30766 169 1 1 1 21393 1 28018 676 13 1 1 7 1 21387 1 12 29352 1 28377 21175 2 1 1 1 22940 21 1 1 1 1 1 2 1 1 1 1 1 1 1 1 32 22032 1 9 1 7263 1 1 33 1 1 1 1 ...
result:
ok 50075 lines
Test #40:
score: 0
Accepted
time: 1066ms
memory: 9816kb
input:
32767 32766 1 2 366062808 1 3 603976360 2 4 590229156 2 5 800736806 3 6 44097753 3 7 328945174 4 8 557936610 4 9 632480701 5 10 577672826 5 11 200453016 6 12 431132615 6 13 454618640 7 14 648582705 7 15 122970083 8 16 30025754 8 17 207861161 9 18 192145853 9 19 75028951 10 20 136159383 10 21 3917683...
output:
1 1 1 3 12609 1 1 4 2 1 2 19058 4 1 1 82 1 166 1 97 1 1 1 1 1 1 12 1 3 73 1 1 1 2 1 3 1 7 1 1 4 34 1 1 1 1 506 1 1 13 1 1 1 28624 1 1 1 1 1 1 1 1 1 8946 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 75 1 1 4 555 10 1 1 1 1 1 24094 1 1 1 1 1 1 1 22 480 1 25777 2 876 1 1 1 1 1 1 1 1 27951 27 6 1 1 21092 3 4 5 2 1 1 3...
result:
ok 50060 lines
Test #41:
score: 0
Accepted
time: 969ms
memory: 9860kb
input:
32767 32766 1 2 526218806 1 3 574084493 2 4 237859344 2 5 141452753 3 6 368924609 3 7 637004921 4 8 605655343 4 9 693060207 5 10 774267027 5 11 361913571 6 12 246425613 6 13 652046016 7 14 732152503 7 15 405990171 8 16 78495161 8 17 295900332 9 18 621532297 9 19 550041506 10 20 590380095 10 21 42581...
output:
2 9 1 1 780 31162 395 5 20000 3 1 31 18076 1 12543 2 1 28058 15999 5 1 14 2 11 15 14505 1 3 12955 1 10641 8590 11525 28146 2 1 1 11 10393 1 1 4326 4 3749 30823 30864 190 2 26697 4 4702 31152 12 17512 19553 4 6361 1 1 22438 1 1 22440 308 1 5 3 10677 1 1 2 2 14183 273 104 177 161 2 174 1 1 113 1 12452...
result:
ok 90025 lines
Test #42:
score: 0
Accepted
time: 1008ms
memory: 9800kb
input:
32767 32766 1 2 954543458 1 3 18121943 2 4 30728674 2 5 916608595 3 6 412861262 3 7 616231888 4 8 27230960 4 9 800190746 5 10 491548327 5 11 276864792 6 12 681168067 6 13 220316323 7 14 129663315 7 15 727981026 8 16 567913703 8 17 92764660 9 18 131826495 9 19 268199078 10 20 544330589 10 21 41005757...
output:
3 2 2 1 3 1 1 5 56 5296 1 4 1 4 1 1 1236 1 22 5 19966 2 12 6 475 28586 1 264 1 1027 1 1 3 1 1 1 1 27701 21136 1 1 1 5011 1 1 1 1 1 1 1 1 1 1 71 3 1 24884 26896 1 1 3 27180 1011 4 1 1 3 5 1 1154 1 1 1 1 27 8552 1 1 9 30626 3 1 3 2092 1 767 1 1 5 1 1 1 29 37 1 2 1 9 4 1 1 1 4 1 1 1 6 31609 7489 1 1 5 ...
result:
ok 90104 lines
Test #43:
score: 0
Accepted
time: 1064ms
memory: 10284kb
input:
32767 32766 1 2 750306444 1 3 886768475 2 4 651477786 2 5 780811636 3 6 879514155 3 7 639920406 4 8 827906566 4 9 246759076 5 10 8902446 5 11 483498857 6 12 311018275 6 13 112196172 7 14 814260430 7 15 672877709 8 16 372626021 8 17 522011729 9 18 598389201 9 19 551905942 10 20 529431530 10 21 234869...
output:
1 25043 8 1 2 1 1 28474 3 1 69 1 6 5173 3 1 1 17360 2 36 52 12 31042 9682 24455 1 1028 1 1 174 16865 16070 12 9 21 1297 7994 28249 19546 25190 3 2 1 12895 1 14822 10669 3 43 26915 3 19 3 3269 8968 26 17515 1 3041 12143 28763 8 450 1 28 17049 1 1 162 10365 1 15990 3 1 3 1 1 1 8461 1 1 1 32132 32 1 22...
result:
ok 9964 lines
Test #44:
score: 0
Accepted
time: 1034ms
memory: 9992kb
input:
32767 32766 1 2 323855288 1 3 625773221 2 4 698582907 2 5 373160258 3 6 923450808 3 7 619147373 4 8 240229172 4 9 353889615 5 10 583326603 5 11 398450078 6 12 262116331 6 13 537609336 7 14 676909617 7 15 593611072 8 16 76330278 8 17 774996257 9 18 145485185 9 19 636459385 10 20 64063610 10 21 255915...
output:
1 31283 1 1 7274 1 1 3 1 1 1 1 1 11 1 16354 1 60 1 30681 9 24 16 1 3 20953 1 1 1 25886 30028 1 2 4 1 1 398 1 14992 25644 27541 4 1 1 1 2 1 26449 1 1 35 1 30707 1 1 187 1 1 119 1 214 12795 1346 1 1 1 2051 301 692 1 11198 19 7101 125 2 1 1 59 1 1 13466 26746 29152 1 1 1 164 2 20139 20192 2 7 1 1 16823...
result:
ok 10060 lines
Subtask #4:
score: 0
Time Limit Exceeded
Test #45:
score: 0
Time Limit Exceeded
input:
50000 100000 35231 1616 822934828 1668 2202 768458723 26049 41810 238904165 15936 42751 466996423 41068 21425 588205829 29502 11760 732391267 13029 44741 930695124 46168 22085 155239713 9505 43779 638894800 18665 43842 298794735 41763 15511 727702105 7865 27776 53447691 32904 34081 844499614 26327 9...
output:
result:
Subtask #5:
score: 13
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #68:
score: 13
Accepted
time: 1644ms
memory: 11100kb
input:
50000 49999 1 2 773336157 1 3 194340376 1 4 40561907 2 5 85673124 3 6 724746156 1 7 416939763 4 8 384948880 7 9 833747431 1 10 4518648 3 11 311221494 5 12 578773527 3 13 320772778 4 14 11680621 14 15 852209440 1 16 532930901 2 17 616508554 12 18 658403193 12 19 366813101 5 20 276295000 7 21 83097661...
output:
34145 2 2 1630 1 2 2 7 4 1 2 1 4 1 48 1 153 1 2 1226 3 24 8 3 1 1 1 1 1 1 82 4 8394 2 19 3 1 1 36647 1 2 2 1 1 2900 14 1 2 1 18 1 13 2 12501 1 16 1 21 20073 262 2 4 5 10 3 1 2 4 1 29 8437 35 1 1550 1 1473 1 2 1 6 13 1 8726 18 17 153 26389 28 3 1 1 2 1 3 94 20 23 1 56 1 1 2 1 1 1 19 5 1 2 13 3 4 1 6 ...
result:
ok 49883 lines
Test #69:
score: 0
Accepted
time: 1821ms
memory: 12668kb
input:
50000 49999 541 8680 217141764 42411 17450 29497259 2922 2367 210454586 42888 46242 141218013 31513 12691 39075415 14443 43750 30174257 32433 2083 24849107 22052 28722 218638133 44265 1646 185675008 30107 2335 20621009 12541 33175 339804815 4109 316 167816804 46420 2599 138763480 1373 39613 11005866...
output:
50000 50000 50000 1253 50000 50000 511 50000 91 21518 50000 50000 24240 50000 50000 5 50000 50000 45135 50000 45876 5742 50000 50000 1 1 2 12346 30 11109 50000 50000 1 50000 4 48872 50000 16 1 50000 50000 2135 50000 50000 1 50000 1 50000 50000 6 50000 71 1 1 50000 50000 2 50000 50000 50000 50000 500...
result:
ok 49970 lines
Test #70:
score: 0
Accepted
time: 1887ms
memory: 10956kb
input:
50000 49999 36327 41883 688572006 21929 4974 528312959 19046 37544 265073551 28063 18603 590341643 12826 32116 630808478 42426 34818 797944744 30992 11239 756872548 16594 9393 347055714 12923 27255 728101884 3466 38095 985921549 30066 45072 313790123 12786 26083 675676126 10051 9213 336178036 30649 ...
output:
1 1 56 5 1 5085 1 2 19 2 1 1 1 3 2 46796 3 29 1 1 13 3 39764 22 47506 1399 1 76 48082 28 4 15 3 85 1 2 1 1 1 1 44571 1 1 10969 2 1316 8 1 1816 1 1 2 1 45 1 219 13257 1 48948 4 1 23 43961 3 1 80 13 1 349 1 1 1 3 48821 1 2436 1 12 4 1 3679 1 48942 12077 1 47 2 22481 47568 1 2 3 45910 10 7 2 4 2 47932 ...
result:
ok 49970 lines
Test #71:
score: 0
Accepted
time: 1725ms
memory: 11128kb
input:
50000 49999 45356 46055 222229657 18891 14106 46041344 6216 9336 108993111 11065 34146 43768553 45232 30811 143991316 42200 33069 48849452 44364 1111 75772099 23278 17601 170969223 9916 4521 164287252 25192 3255 273246573 39276 28125 308565624 46267 40316 7392430 27354 7565 142314468 22639 42466 198...
output:
1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 10 1 1 1 1 1 3 2065 1 1 1 1 1 14 1 2 1 6 12034 1 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 46655 12 1 42969 1 1 1 1 1 1 3 1 1 1 1 1 2 1 3 1 1 1 1 1 1 1 34920 1 1 8 1 1 1 1 1 2 1 12 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 3839 1 26988 1 1 1 1 1 1 1 1 1 1 1 45262 1 12 1 1 1 1 1 1 1 ...
result:
ok 50014 lines
Test #72:
score: 0
Accepted
time: 1804ms
memory: 11016kb
input:
50000 49999 45895 3922 71902426 21874 14474 197348243 39626 34823 51434808 5189 6472 12708634 36193 1872 58453465 26063 7150 141846401 18760 28835 38331526 32874 21952 145776113 1122 49427 87692578 41696 3543 95256733 7963 500 32486178 16249 41532 71644540 26431 19428 274682273 34698 31060 149686448...
output:
2 10 2 4 1 50000 11 3 18 50000 1 1 50000 11 2 6 2 1 50000 33 50000 50000 22 50000 1 50000 4 6 2 2 2 5 18 1 2 2 20 2 1 50000 6 1 71 194 50000 2 50000 50000 54 6 50000 2 25 50000 5 18 3 57 3 14 33 31 1 6 62 3 9 147 10 356 44 5 7 10 2 50000 50000 1 27 3 7 50000 50000 50000 1 2 3 2 2 50000 5 50000 50000...
result:
ok 49970 lines
Test #73:
score: 0
Accepted
time: 1844ms
memory: 10876kb
input:
50000 49999 35341 13520 17141764 26545 49269 29497259 16246 22640 110454586 35433 46589 141218013 5786 1083 189075415 4466 48857 30174257 11816 6000 24849107 3107 31468 68638133 19886 14823 85675008 48925 7887 70621009 32929 10764 39804815 27178 8517 417816804 26641 43632 38763480 35866 38748 110058...
output:
7 5 12 1 1 5 1 50000 2 50000 50000 6 22 50000 2 50000 50000 4 4 2 1 50000 2 1 106 31 57 31 1 13 50000 50000 50000 52 50000 1 260 50000 4 50000 1 3 50000 29 50000 11 15 2 13 1 81 50000 19 50000 50000 25 6 50000 50000 12 6 5 5 10 4 1 50000 5 6 6 1 50000 4 50000 25 2 5 50000 50000 4 2 8 50000 3 81 354 ...
result:
ok 49970 lines
Test #74:
score: 0
Accepted
time: 1867ms
memory: 10996kb
input:
50000 49999 25529 24861 71902426 32875 12248 86237132 15921 39212 273657030 28320 39686 123819745 35421 694 58453465 14424 5372 141846401 1812 36451 149442637 6965 15454 145776113 4884 14172 87692578 35538 26406 95256733 22100 30598 143597289 14130 47258 182755651 17570 17146 52460051 22098 17556 14...
output:
2 2 3 7 5 50000 58 9 30 4 1 1 4 50000 8 1 20 1 3 50000 1 50000 30 16 5 50000 24 2 50000 2 3 1 2 1 14 50000 34 50000 22 1 50000 36 80 236 1 50000 7 50000 18 50000 6 2 17 4 6 12 2 38 50000 2 74 4 2 50000 136 50000 1 114 2 50000 50000 3 2 15 1 4 50000 6 16 1 7 50000 50000 31 8 6 9 50000 1 202 4 50000 1...
result:
ok 49970 lines
Test #75:
score: 0
Accepted
time: 1817ms
memory: 11216kb
input:
50000 49999 45895 3922 556486138 21874 14474 500239109 39626 34823 813918810 5189 6472 676494674 36193 1872 630808478 26063 7150 457864078 18760 28835 11366687 32874 21952 788882333 1122 49427 933153048 41696 3543 184270819 7963 500 759242048 16249 41532 933865474 26431 19428 814065727 34698 31060 4...
output:
2 137 2 2 7 4 4 9 11 7 1 2 1 1 2 11 105 5 1 1 8 7 3 1 1 1 20 1 2 27 3 1 4 3 1 1 6 4 1 2 1 7 2 6 1 76 43 1 1 5 1 7 1 1 29 1 1 2 1 1 6 1 4 6 2 26 5 2 5 1 1 1 2 7 2 36 1 4 5 1 1 2 49494 1 1 2 3 4 18 8 2 5 25 42 15 8 1 2 48982 2 1 1 2 4 5 4 2 111 1 1 1 1 1 8 2 4 1926 11 1 3 6 2 13 3 1 3 2 1 1 2 33 1 2 1...
result:
ok 49970 lines
Test #76:
score: 0
Accepted
time: 1843ms
memory: 11456kb
input:
50000 49999 35341 13520 695714444 26545 49269 528312959 16246 22640 914303724 35433 46589 698821037 5786 1083 734408363 4466 48857 690584088 11816 6000 609868641 3107 31468 347055714 19886 14823 728101884 48925 7887 557096411 32929 10764 133121824 27178 8517 765140958 26641 43632 336178036 35866 387...
output:
3 2 1 27 1 4 6 2 1 1 1 1 42 1 8 129 1 18 1 23 5 1 2 2 1 98 1 1 5 1 1 1 44 1 3 13 1 1 1 1 2 1 1 1 1 5 2 11 3 5 1 8 1 1 1 3 22 1 49373 2 4 8 1 3 1 2 3 2 1 1 4 1 111 49287 1 1 4 1 2 8 1 10 49369 2 1 8 1 3 48519 1 6 2 2 3 2 1 4 1 2 1 1 21 91 1 1 4 5 1 1 7 1 145 1 6 10 4 1 1 3 252 1 2 1 3 1 1 47 13 2 5 1...
result:
ok 49970 lines
Test #77:
score: 0
Accepted
time: 1773ms
memory: 11172kb
input:
50000 49999 25529 24861 454246504 32875 12248 528312959 15921 39212 584049702 28320 39686 398236797 35421 694 630808478 14424 5372 779472977 1812 36451 866549529 6965 15454 788882333 4884 14172 933153048 35538 26406 184270819 22100 30598 126730895 14130 47258 485611323 17570 17146 482753900 22098 17...
output:
3 133 1 4 5 7 168 10 6 2 215 1 14 2 2 2 1 1 3 1 1 1 1 1 1 1 39 1 48792 22 2 2 70 1 1 1 1 3 2 5 41 4 2 2 3 8 1 1 1 1 10 1 2 1 5 1 4 8 49329 3 2 9 1 8 2 1 2 1 6 102 1 19 2 7 1 2 3 6 124 1 2 1 49329 3 84 22 4 2 3 1 2 1 15 4 1 2 173 2 48672 3 1 2 2 4 4 5 2 3 2 2 13 1 142 2 1 1 2 6 2 1 1 25 1 3 8 3 72 1 ...
result:
ok 49970 lines
Test #78:
score: 0
Accepted
time: 1736ms
memory: 11052kb
input:
50000 49999 45895 3922 259666452 21874 14474 99678318 39626 34823 34014426 5189 6472 88980800 36193 1872 98545108 26063 7150 257073367 18760 28835 96275478 32874 21952 10925241 1122 49427 131362924 41696 3543 7390389 7963 500 47191743 16249 41532 212104466 26431 19428 34881854 34698 31060 24950387 2...
output:
10 1 4 1 2 1 1 1 1 1 1 4 5 7 2 1 1 1 6 1 1 1 40 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 4 1 1 12 1 2 4 2 48 571 3 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 7 2 1 1 1 4 1 1 2 1 24 13 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 2 1 3 1 1 1 1 1 1 1 1 4 2 1 1 1 2 1 1 1 1 78 1 3 1 1 1 5 1 1 1 1 1 1 ...
result:
ok 50014 lines
Test #79:
score: 0
Accepted
time: 1754ms
memory: 12548kb
input:
50000 49999 35341 13520 22229657 26545 49269 46041344 16246 22640 158993111 35433 46589 93768553 5786 1083 143991316 4466 48857 248849452 11816 6000 175772099 3107 31468 20969223 19886 14823 64287252 48925 7887 73246573 32929 10764 8565624 27178 8517 7392430 26641 43632 92314468 35866 38748 11985288...
output:
1 1 5 4 1 1 13 1 7 6 1 1 1 3 11 1 1 1 1 1 1 1 1 3 1 1 2 1 133 8 1 1 1 3 6 1 1 1 1 1 23 1 1 1 2 2 2 1 1 1 1 1 1 1 2 188 1 1 94 1 1 1 1 2 22 1 1 1 1 24 1 2 2 9 10 1 1 1 12 1 1 8 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 4 44 1 1 1 1 1 1 1 1 4 9 1 30 1 1 1 1 1 2 1 1 1 34 1 349 1 1 3 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 ...
result:
ok 50014 lines
Test #80:
score: 0
Accepted
time: 1724ms
memory: 10840kb
input:
50000 49999 25529 24861 148555341 32875 12248 99678318 15921 39212 367347759 28320 39686 422314133 35421 694 98545108 14424 5372 145962256 1812 36451 207386589 6965 15454 10925241 4884 14172 131362924 35538 26406 7390389 22100 30598 158302854 14130 47258 323215577 17570 17146 34881854 22098 17556 24...
output:
1 1 1 1 1 1 1 1 1 1 1 1 5 8 1 1 1 1 1 1 1 1 1 1 1 2 1 1 10 1 1 1 1 1 1 1 1 1 1 4 1 3 1 1 1 1 1 7 1 1 1 1 14 243 1 10 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 47 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 2 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 44 13 2 1 1 1 5 1 1 1 1 1 1 1 ...
result:
ok 50014 lines
Test #81:
score: 0
Accepted
time: 1690ms
memory: 10876kb
input:
50000 49999 45895 3922 30361418 21874 14474 104392820 39626 34823 83430888 5189 6472 8200216 36193 1872 35020678 26063 7150 130732294 18760 28835 51239548 32874 21952 2644170 1122 49427 10705266 41696 3543 2533765 7963 500 138055955 16249 41532 167525357 26431 19428 109064387 34698 31060 153448620 2...
output:
1 5 3 1 1 3 1 1 55 1 1 1 1 1 82 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 39 1 1 1 8 1 1 1 1 1 1 191 1 1 10 2 1 1 1 194 1 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 3 2 2 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 24 1 1 4 5 2 1 1 1 1 1 1 1 3 43 6 1 19 1 1 1 1 1 1 1 1 4 4 1 1 1 10 1 1 1 13 1 1 26 1 1 1 1 1 2 5 1 1 1 1 16 1...
result:
ok 89915 lines
Test #82:
score: 0
Accepted
time: 1762ms
memory: 9880kb
input:
50000 49999 35341 13520 75189991 26545 49269 49720500 16246 22640 109063178 35433 46589 160669811 5786 1083 246966388 4466 48857 38043514 11816 6000 149655265 3107 31468 92981554 19886 14823 58818510 48925 7887 39848603 32929 10764 46941811 27178 8517 388330335 26641 43632 49423087 35866 38748 26353...
output:
1 1 1 1 33 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 5 1 4 8 1 1 1 164 1 3 1 1 1 1 11 4 1 7 1 1 2 1 1 1 1 1 1 1 1 1 1 1 17 1 1 1 14 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 5 31 1 15 1 1 1 3 1 1 6 1 1 1 1 3 1 1 1 1 1 1 3 52 1 1 5 1 1 1 12 1 129 1 1 1768 1 1 1 1 1 1 1 1 4 1 1 2 3 1 1 1 1 4 1 1...
result:
ok 89915 lines
Test #83:
score: 0
Accepted
time: 1700ms
memory: 9768kb
input:
50000 49999 25529 24861 141472529 32875 12248 104392820 15921 39212 305653110 28320 39686 119311327 35421 694 35020678 14424 5372 130732294 1812 36451 273461770 6965 15454 2644170 4884 14172 10705266 35538 26406 2533765 22100 30598 138055955 14130 47258 167525357 17570 17146 109064387 22098 17556 15...
output:
1 1 4 1 1 1 1 1 84 1 1 1 1 1 139 1 1 1 1 1 1 2 1 1 1 1 1 33 1 1 1 1 56 1 1 1 14 1 1 1 1 1 1 308 1 1 5 1 1 1 3 188 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 13 1 1 3 1 57 1 15 8 17 2 1 1 1 1 12 14 1 5 2 7 3 1 1 2 1 2 1 1 1 29 5 1 1 1 1 2 1 4 1 1 1 6 4 1 1 1 4 1 2 1 3 1 1 30 1 1 1 1 2 1 1 1 1 1 1 ...
result:
ok 89915 lines
Test #84:
score: 0
Accepted
time: 1652ms
memory: 10920kb
input:
50000 49999 45895 3922 328676792 21874 14474 164151658 39626 34823 110423795 5189 6472 309826180 36193 1872 41504476 26063 7150 265344632 18760 28835 3767059 32874 21952 45068961 1122 49427 136598663 41696 3543 185438 7963 500 59485429 16249 41532 161817297 26431 19428 78346162 34698 31060 74148359 ...
output:
1 1 1 1 1 1 1 1 1 1 15 1 1 1 1 1 1 14 15 1 7 2 1 1 1 61 1 1 15 1 1 1 25 2 5 6 1 7 1 1 33 1 3 2 1 1 1 1 1 1 1 28 12 1 1 49 1 1 1 11 1 1 2 8 1 1 1 1 1 1 1 5 2 4 1 20 7 2 1 1 2 1 2 1 1 1 1 1 1 9 1 2 1 1 1 1 1 1 1 1 1 1 27 1 3 1 1 2 1 5 1 1 1 1 1 3 2 1 1 1 7 1 5 16 1 1 1 1 1 6 1 1 1 1 14 1 1 1 4 10 1 1 ...
result:
ok 10049 lines
Test #85:
score: 0
Accepted
time: 1658ms
memory: 11372kb
input:
50000 49999 35341 13520 44501821 26545 49269 57371778 16246 22640 8148124 35433 46589 84398518 5786 1083 118590011 4466 48857 57675455 11816 6000 180842678 3107 31468 80673773 19886 14823 23138841 48925 7887 67737102 32929 10764 199468875 27178 8517 45842433 26641 43632 17024200 35866 38748 18946241...
output:
1 2 1 1 1 1 8 1 4 16 1 3 1 1 1 1 1 1 1 1 3 1 1 1 1 2 10 10 1 1 1 1 3 8 13 1 2 1 1 1 1 1 6 1 4 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 49 1 1 1 2 1 1 1 1 1 1 1 1 104 1 1 79 1 2 1 5 1 1 1 1 1 13 5 1 1 1 1 1 1 1 5 1 1 1 1 1 3 1 2 1 1 1 2 1 1 1 46 3 1 1 1 1 1 24 16 2 1 1 41 1 1 1 6 1 2 7 1 1 18 1 23 1 155...
result:
ok 10049 lines
Test #86:
score: 0
Accepted
time: 1666ms
memory: 11116kb
input:
50000 49999 25529 24861 217565681 32875 12248 53040547 15921 39212 443757128 28320 39686 87603958 35421 694 41504476 14424 5372 154233521 1812 36451 448211503 6965 15454 45068961 4884 14172 136598663 35538 26406 185438 22100 30598 59485429 14130 47258 272928408 17570 17146 78346162 22098 17556 74148...
output:
1 2 1 1 1 1 16 1 1 1 12 3 1 1 1 1 1 13 7 1 2 3 1 1 1 36 1 1 25 15 1 1 41 1 1 1 1 9 1 1 3 1 1 4 1 1 1 1 1 1 1 86 4 1 1 73 1 1 1 51 1 1 1 133 1 2 1 1 1 1 1 2 7 1 1 4 29 20 1 1 11 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 9 1 1 1 5 1 1 1 1 1 9 1 1 7 32 1 1 1 11 1 3 144 1 1 2 1 6 4 1 1 2 1 1 1 1 1 2 24 ...
result:
ok 10049 lines
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%