QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100162 | #185. Bridges | Bronya | 44 | 1452ms | 15400kb | C++20 | 2.7kb | 2023-04-24 20:36:45 | 2023-04-24 20:36:51 |
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+1;
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)*__lg(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: 2ms
memory: 5688kb
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: 2ms
memory: 5780kb
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: 2ms
memory: 5748kb
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: 0ms
memory: 5648kb
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: 19ms
memory: 3980kb
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: 6ms
memory: 3852kb
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: 13ms
memory: 3848kb
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: 12ms
memory: 3852kb
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: 13ms
memory: 5740kb
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: 10ms
memory: 5800kb
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: 13ms
memory: 5704kb
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: 14ms
memory: 5772kb
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: 13ms
memory: 5692kb
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: 14ms
memory: 5796kb
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: 17ms
memory: 5780kb
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: 16ms
memory: 5776kb
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: 15ms
memory: 5780kb
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: 13ms
memory: 5832kb
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: 16ms
memory: 5824kb
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: 0
Time Limit Exceeded
Test #20:
score: 16
Accepted
time: 1188ms
memory: 10984kb
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: 1291ms
memory: 10148kb
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: 1293ms
memory: 10640kb
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: 1418ms
memory: 10648kb
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: 1452ms
memory: 10468kb
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: -16
Time Limit Exceeded
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:
result:
Subtask #3:
score: 17
Accepted
Test #33:
score: 17
Accepted
time: 956ms
memory: 9208kb
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: 678ms
memory: 7584kb
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: 1049ms
memory: 8780kb
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: 920ms
memory: 9292kb
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: 34ms
memory: 6676kb
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: 1035ms
memory: 9224kb
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: 859ms
memory: 9760kb
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: 794ms
memory: 8928kb
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: 490ms
memory: 8584kb
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: 432ms
memory: 8824kb
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: 606ms
memory: 9620kb
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: 529ms
memory: 9600kb
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: 14
Accepted
Test #45:
score: 14
Accepted
time: 1072ms
memory: 13884kb
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:
2 2 1 48165 37106 1 48830 1 47126 3 37777 1 14 1 1 24 1 48755 44817 17617 24322 48909 7 47708 1 41147 48949 45939 48022 1 26304 1 1 22363 24527 46076 37978 1 1 2 44508 1 47625 48554 1 2 4 48711 48431 41315 2 2 9364 3 37323 46978 39881 32373 5 39140 47126 44635 47960 1 48141 47192 28 27190 38467 4 48...
result:
ok 100000 lines
Test #46:
score: 0
Accepted
time: 41ms
memory: 7840kb
input:
1 0 100000 2 1 449565301 2 1 418018081 2 1 566914037 2 1 386096903 2 1 325815043 2 1 515513392 2 1 349622300 2 1 5042450 2 1 469351640 2 1 219472495 2 1 510850771 2 1 885705436 2 1 594457820 2 1 410756749 2 1 959667810 2 1 479458147 2 1 705147675 2 1 140732217 2 1 281668854 2 1 333164650 2 1 3934393...
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 #47:
score: 0
Accepted
time: 495ms
memory: 11324kb
input:
447 99681 432 259 741787656 82 143 380113631 317 104 156765724 76 270 110432834 212 261 207353276 25 300 39463185 14 56 725978322 155 236 785136504 398 265 446396092 343 1 949863738 1 110 808326751 97 180 623625192 308 92 73346434 253 252 319943247 362 372 874189144 206 402 177923890 22 205 89269820...
output:
447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 446 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 447 272 447 ...
result:
ok 10000 lines
Test #48:
score: 0
Accepted
time: 250ms
memory: 11324kb
input:
447 99681 432 259 1000000000 82 143 1000000000 317 104 1000000000 76 270 1000000000 212 261 1000000000 25 300 1000000000 14 56 1000000000 155 236 1000000000 398 265 1000000000 343 1 1000000000 1 110 1000000000 97 180 1000000000 308 92 1000000000 253 252 1000000000 362 372 1000000000 206 402 10000000...
output:
443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 443 ...
result:
ok 10000 lines
Test #49:
score: 0
Accepted
time: 721ms
memory: 13460kb
input:
50000 100000 36430 26409 3 14637 42323 4 4352 35569 1 14530 43949 2 22805 22365 1 49910 3378 4 1494 5088 2 18398 11098 5 14316 10284 5 11863 11681 2 29896 36912 3 30517 45099 4 36259 16961 1 40065 27965 2 2717 46870 3 34358 5004 1 3460 37101 2 13920 793 1 23824 38760 2 47941 20057 1 25012 1567 2 377...
output:
2 48980 48980 48980 2 48980 46861 46861 2 46861 39197 1 39197 46861 48980 2 18 1 48980 39197 48980 39197 39197 46861 8 48980 39197 46861 13013 39197 46861 39197 48980 48980 39197 39197 48980 48980 39197 39197 1 4 46861 48980 1 46861 46861 1 1 48980 78 13013 39197 46861 48980 46861 5 46861 39197 1 2 ...
result:
ok 100000 lines
Test #50:
score: 0
Accepted
time: 998ms
memory: 15400kb
input:
50000 100000 36430 26409 891600895 14637 42323 146361404 4352 35569 221787293 14530 43949 358568724 22805 22365 190650305 49910 3378 414088144 1494 5088 592528192 18398 11098 542270793 14316 10284 350034541 11863 11681 878653236 29896 36912 168210793 30517 45099 365684348 36259 16961 960673881 40065...
output:
1 48294 4 20863 1 43446 48305 48732 46205 44911 48772 48525 21 44625 42513 48262 22234 46164 1 1 1 41815 1 44908 3 42859 47778 27167 48693 1 43420 2 47449 1 3 1 48843 2 1 47884 2 5 41904 1 42400 46059 4 2 1 30131 42694 11231 1 1 48952 1 37568 40717 1 44503 1 46559 1 47010 39169 42073 42791 1 1 26772...
result:
ok 100000 lines
Test #51:
score: 0
Accepted
time: 701ms
memory: 14164kb
input:
50000 100000 36430 26409 3 14637 42323 1 4352 35569 3 14530 43949 3 22805 22365 3 49910 3378 4 1494 5088 3 18398 11098 4 14316 10284 6 11863 11681 1 29896 36912 1 30517 45099 6 36259 16961 1 40065 27965 1 2717 46870 1 34358 5004 2 3460 37101 2 13920 793 1 23824 38760 3 47941 20057 2 25012 1567 4 377...
output:
39450 11923 39450 48980 46957 11923 39450 46957 48980 48980 1 1 46957 39450 39450 48980 46957 98 46957 48980 48980 48980 1 48980 48980 39450 39450 46957 46957 46957 11923 46957 48980 4 1 48980 48980 46957 1 1 11923 48980 46957 48980 48980 48980 48980 39450 48980 1 11923 48980 1 39450 46957 1 11923 3...
result:
ok 100000 lines
Test #52:
score: 0
Accepted
time: 440ms
memory: 9736kb
input:
50000 50000 3018 2466 31856784 44110 19797 43049494 29377 21015 99965770 18756 28173 453546998 30313 33813 132485681 29934 42387 8136444 24167 31408 174713487 21584 31531 8206037 37467 45599 1224360 19205 26080 254678499 3769 35418 112134933 8806 44621 74762896 15381 26395 186780991 30397 3214 31302...
output:
37 21 1 1 5 8 66 19 3 3 17 2 3 1 8 15 2 1 3 2 146 11 47 3 1 2 2 3 8 3 7 3 1 27 4 1 1 2 4 1 1 1 2 4 1 3 1 3 1 2 2 1 1 4 3 2 3 1 2 139 6 2 1 1 4 1 1 6 1 5 2 26 1 1 1 81 1 1 3 1 2 2 4 1 414 4 14 1 1 7 1 1 2 1 4 15 4 15 1 1 1 2774 9 8 3 4 35 5 3 4 6 2 9 4 1 1 1 50 35 115 2 33 7 3 3 1 2 1 1 138 2 3 3 15 ...
result:
ok 100000 lines
Test #53:
score: 0
Accepted
time: 432ms
memory: 9796kb
input:
50000 50000 3018 2466 986978263 44110 19797 568890536 29377 21015 499670939 18756 28173 839504998 30313 33813 296515410 29934 42387 607104763 24167 31408 819593187 21584 31531 932588647 37467 45599 781307391 19205 26080 840849964 3769 35418 172098007 8806 44621 514674542 15381 26395 631793541 30397 ...
output:
2 5 7 2 10 1 4 2 3 1 2 1 1 1 1 2 1 1 11 1 1 39 8 6 1 11 4 1 1 3 1 3 5 1 2 9 1 2 2 18 17 2 1 1 2 1 1 1 3 2 12 2 8 8 3 9 10 15 1 10 75 1 2 29 1 2 1 402 78 1 17 2 1 6 13 2 3 11 1 2 2 2 4 1 2 5 3 2 4 2 4 3 3 1 1 1 2 3 1 1 1 3 3 4 10 1 1 9 21 1 1 4 12 4 11 2 1 1 2 4 1 2 1 3 9 2 25 3 6 3 2 12 1704 2 3 4 2...
result:
ok 100000 lines
Test #54:
score: 0
Accepted
time: 443ms
memory: 9796kb
input:
50000 50000 3018 2466 79153577 44110 19797 74388894 29377 21015 68432062 18756 28173 253920608 30313 33813 96749945 29934 42387 211811490 24167 31408 260503273 21584 31531 6623362 37467 45599 10982747 19205 26080 299300783 3769 35418 193906707 8806 44621 101185330 15381 26395 375628184 30397 3214 30...
output:
17 106 67 624 499 2727 182 556 365 801 128 3016 835 25 429 79 301 1186 23 189 10 2 362 17 147 896 88 125 176 77 536 429 352 348 61 98 1061 94 499 2229 79 143 440 16 14 47 40 53 374 215 22 89 2858 55 379 756 218 268 17 191 13 5 1359 232 46 247 105 918 105 1442 243 6 52 1246 17 449 560 115 37 37 57 65...
result:
ok 100000 lines
Test #55:
score: 0
Accepted
time: 722ms
memory: 11632kb
input:
50000 75000 33889 6094 187797790 6038 24958 249870404 39193 12649 47857772 404 6521 64489103 45477 33178 61611498 33350 45699 89159626 39479 5160 5857314 18313 12942 59456592 16738 45598 162999431 6188 46675 375553080 5923 47352 267640 18352 44726 24162741 25970 36584 160755499 21001 12852 115486368...
output:
1 5 6944 1 62 300 9 1 8 4 1 33 35 12 40 324 39 79 1 1 1 203 1 1 151 2 2 1156 390 1 2106 19 2 1 1 3 1 1 4 522 25 2 1 1 5 5 4 6 136 300 8 1 15 5 6781 4 1 50 64 1 6 1 2 3 17 3 67 2 1 3 4 961 7 2 42 2033 1 4 45 128 1 1 1 31 4 2 8 26 7 30 1 1 6781 1 46 63 185 1 2 1 328 11 28 491 16 14 2 156 284 63 41 1 1...
result:
ok 100000 lines
Test #56:
score: 0
Accepted
time: 686ms
memory: 12532kb
input:
50000 75000 33889 6094 420893227 6038 24958 452093259 39193 12649 817331307 404 6521 852910965 45477 33178 817357513 33350 45699 743854302 39479 5160 973119288 18313 12942 823671581 16738 45598 734695190 6188 46675 440713089 5923 47352 358615002 18352 44726 690405567 25970 36584 376493341 21001 1285...
output:
1 8 1 5 9 1 478 6 4 43 8 88 5 2 1 2 6 12 13 17 2 1 4 2 630 2 39 7 5 58 2 1 382 2822 6 1 11 1506 48 8 7 3 10 3 1 38 1 7 4 2 1 364 3 488 16 60 10 1 9 2 11 23 19 6 1 12 20 1 54 1 3 158 5 2473 1 1 834 1 29 1 1 23 4 361 1247 414 1 4 2 80 2 67 1 1 4 1 258 16 2 82 4 3 18 67 76 5046 138 7 1 18 2 1 8 2 1 1 1...
result:
ok 100000 lines
Test #57:
score: 0
Accepted
time: 735ms
memory: 12192kb
input:
50000 75000 33889 6094 312238223 6038 24958 105159308 39193 12649 70014492 404 6521 268819182 45477 33178 30294724 33350 45699 23408487 39479 5160 170044358 18313 12942 462115817 16738 45598 12945966 6188 46675 50759466 5923 47352 10756786 18352 44726 445834887 25970 36584 110254109 21001 12852 1876...
output:
1960 5423 1339 372 4065 5678 3450 3878 3296 2348 2416 2056 3398 2913 11761 2721 18563 5 2913 2905 3752 1974 13388 5423 3076 1689 1974 614 5423 3450 3449 3878 123 5423 48 18563 14 1177 6 1603 19 2146 1339 3749 443 5423 3537 2914 4065 519 2416 3449 3450 887 2720 3810 10743 5423 4262 37 102 536 1556 11...
result:
ok 100000 lines
Test #58:
score: 0
Accepted
time: 596ms
memory: 14332kb
input:
50000 100000 15902 37902 1 17114 1173 1 11644 26158 1 19786 42295 1 7375 13869 1 41274 22976 2 835 37821 2 43555 33134 1 43468 19565 1 9379 47294 1 16398 11626 2 38982 40565 2 37286 12116 1 47601 37754 2 48429 36718 1 42177 6120 1 4654 18153 2 18980 25667 2 14661 40435 2 32390 8457 1 21754 24732 1 4...
output:
48953 39613 39613 48953 48953 48953 39613 1 48953 1 39613 4 48953 48953 39613 48953 48953 39613 39613 39613 39613 48953 39613 48953 39613 48953 48953 39613 48953 48953 48953 48953 39613 39613 39613 39613 39613 39613 39613 39613 48953 39613 48953 39613 39613 48953 39613 39613 2 48953 48953 39613 3961...
result:
ok 100000 lines
Test #59:
score: 0
Accepted
time: 625ms
memory: 13744kb
input:
50000 100000 16622 4042 3 29296 26235 1 924 10146 2 6673 2735 1 7465 16111 1 39191 3402 1 31557 2062 3 41332 16451 1 40029 29774 1 1536 11606 1 9816 21897 2 15118 49569 3 22016 42191 1 37712 3855 2 22722 21172 1 3261 35636 2 38376 20812 2 5328 40248 3 33365 373 3 29011 31608 1 25458 39541 3 22685 16...
output:
1 22819 49028 45603 49028 49028 45603 45603 1 49028 45603 45603 45603 49028 49028 49028 22819 49028 22819 45603 22819 49028 2 49028 22819 45603 45603 2 1 49028 49028 49028 49028 71 49028 1 49028 49028 4 45603 45603 49028 9 22819 45603 49028 22819 22819 49028 49028 17 22819 49028 1 49028 1 45603 4560...
result:
ok 100000 lines
Test #60:
score: 0
Accepted
time: 1046ms
memory: 13440kb
input:
49729 99012 34054 8341 4175351 18682 17977 31563632 19269 15971 316486513 16453 23315 222200372 48031 37963 328549397 35957 4042 144188344 41481 23139 199796339 30840 7454 2956883 9107 36464 105802625 15976 35553 213475524 35520 40158 41633125 27542 9944 262538992 14658 21385 146413217 27915 22932 1...
output:
162 1 152 40185 3 49369 1 43082 40012 13825 2 2 1 37937 37355 8 162 48318 1 1 40417 44848 48355 49114 81 49678 1 49166 1 47344 49715 7 5 49689 11981 46554 49369 1 48326 2326 49608 40335 3 1 10 3 6 9 44579 33623 1 49276 1 40358 1 32187 45056 178 1533 1 40012 39683 8 31113 7 23739 1153 20 7 28 49729 1...
result:
ok 100000 lines
Test #61:
score: 0
Accepted
time: 1035ms
memory: 15172kb
input:
49719 98972 21767 6065 50070961 20464 17361 169248081 27314 45549 36819446 33702 41335 351272826 48558 44834 199266519 30638 21034 674557652 19478 11122 253122173 29904 49011 156855128 47670 28852 109873392 17146 14684 169743003 15703 3814 7374462 16769 39749 189412976 7203 46682 136468490 46010 203...
output:
1 1 1 2 26 147 49689 23561 41142 18 1 1 41021 49054 1 2 42761 1 10756 40184 48557 3 1 5 33981 10933 49719 1 24618 41535 1 25 54 44299 5 858 43743 21961 8665 19 27734 43186 11 23 1 34874 1 49646 1 2 48268 45 49640 48808 1 26597 2 45151 103 1 49615 1 1 1 174 13552 5 48804 48896 10 18 19 2 21753 7 2308...
result:
ok 100000 lines
Test #62:
score: 0
Accepted
time: 1059ms
memory: 14020kb
input:
50000 99400 29410 30330 758567223 17803 21820 941403915 14061 46028 280515052 37193 24091 781060591 25716 20072 882860054 33445 37640 509782731 12541 23219 782716806 18523 6908 531828972 3230 32030 421168543 44552 48693 97642726 1279 2726 643181026 25106 34578 884629614 4038 37779 617488416 38071 11...
output:
49998 9 8 47672 29100 1 1 132 49992 1 7 46808 49976 49726 49996 40748 3 1 48367 6 2 1 3274 49999 992 1207 1 30090 47305 264 2 49642 1 28732 34285 49908 49963 49449 40622 1 49946 2 1 49775 49916 27 49986 85 1 39594 533 49933 1 1 32602 2 49190 49982 2 1 1 46823 3 1 48896 656 16 49594 26850 14 49952 3 ...
result:
ok 100000 lines
Test #63:
score: 0
Accepted
time: 1015ms
memory: 13916kb
input:
49950 99201 36281 36503 763054174 9379 38035 472773481 25806 36188 761440834 24770 43939 593827712 44117 32984 959406044 18886 41008 690486926 49627 4512 624530349 21092 16661 833081827 14094 49233 910931467 31376 2432 747917920 26336 18969 451935820 39553 16163 535086746 26124 43554 903283220 6256 ...
output:
9 49763 219 9 24398 46296 46900 1 1 1 93 5916 2 11 10 18101 49510 49887 1 382 16 49804 1 47896 1 48983 46558 17 48189 1 3151 2988 16 9151 4 46488 1 26 49529 5082 49830 16 7 13 39175 49618 1 87 2 49021 17 2 7804 22087 47920 1 19 1 46104 49549 12010 49940 1 49365 49944 3451 1 16304 48850 39516 49950 1...
result:
ok 100000 lines
Test #64:
score: 0
Accepted
time: 832ms
memory: 13284kb
input:
49998 83327 39504 32115 603170071 49865 30849 130675480 30107 3167 55412622 33018 6097 94561562 32270 43450 124904278 1328 13459 79410517 5277 31217 436853542 22995 17298 247419872 32399 25864 535304576 20487 35769 11662754 19774 21657 33814282 4158 30463 363491899 40211 40065 187002697 22211 32071 ...
output:
4987 4981 13971 16566 34472 16568 15966 34464 1391 15951 34475 15951 48451 8373 6473 49998 8622 8956 8373 8373 49998 8622 8373 15970 15992 6 4960 8622 13975 15966 16568 8956 8606 34469 8373 13975 8956 8373 34464 4960 4960 5006 15951 15966 285 4989 6446 16568 8962 988 34472 6463 15968 33095 15966 861...
result:
ok 100000 lines
Test #65:
score: 0
Accepted
time: 843ms
memory: 12672kb
input:
49992 83306 18171 44476 566111419 14354 45323 78491664 31324 42407 86408010 16269 10214 343483203 44837 22800 14793460 45715 9529 8321488 22348 19511 683659900 7036 10120 683944755 9747 12255 43970763 37546 33897 19677943 12388 12210 109434184 24731 34404 33575744 46477 2587 10649026 26986 49355 534...
output:
13375 13386 49992 9092 13500 14470 13375 13375 3112 11001 11018 4113 11002 9110 13386 13497 11001 1292 49992 13380 11002 9119 11018 3108 13289 49992 13384 13289 49992 13391 11001 1116 13384 9094 10949 3112 13375 13386 9094 821 9109 9110 9110 10999 13392 13380 13386 49992 11013 11000 22123 11001 1101...
result:
ok 100000 lines
Test #66:
score: 0
Accepted
time: 1014ms
memory: 14068kb
input:
48729 95081 34569 31119 121468261 44534 42997 32387101 27645 27262 179917793 27160 40400 147086695 24917 45974 392357817 10176 23589 64525446 36132 43032 101470030 48191 26960 218513742 27615 10820 393845101 36869 33441 37211419 40354 27469 38639025 14212 10067 288238270 17744 3968 186572229 24158 3...
output:
48488 47027 46935 46745 44133 43798 47943 1 47759 48461 48565 47726 42357 5 46497 46616 48729 48729 45359 1 48723 47960 46479 48476 47710 1 46777 48729 47331 3 47730 48709 42890 44349 48596 46030 48637 42242 47498 47057 48605 48729 48157 45068 45560 9 48150 48729 48367 48729 46030 48691 48711 48709 ...
result:
ok 100000 lines
Test #67:
score: 0
Accepted
time: 712ms
memory: 12700kb
input:
44729 80122 5199 20293 31 7817 41640 6 34878 22640 20 40005 33324 15 40383 32872 13 34683 29204 20 27984 14878 12 30253 38386 33 25606 20784 8 2189 25911 7 2456 33868 20 11948 9644 40 20299 36926 11 33341 21039 30 32405 33498 16 19620 43993 12 6437 37553 50 13577 29531 25 18855 28841 64 10313 6994 2...
output:
43932 43932 44630 44400 43932 44720 43932 44720 43932 44400 44630 44400 44630 44720 44400 44400 44630 44720 44720 43932 44630 44400 44720 43932 44720 44720 43932 44720 44630 44400 44630 44400 44630 43932 44630 44630 43932 44720 44400 44720 43932 44720 44400 43932 43932 44630 44400 43932 44400 1 4393...
result:
ok 100000 lines
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%