QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#535624	#9159. 登山	yanshanjiahong	5	34ms	11136kb	C++20	3.8kb	2024-08-28 11:21:57	2024-08-28 11:21:57

Judging History

你现在查看的是最新测评结果

[2024-08-28 11:21:57]
评测

测评结果：5
用时：34ms
内存：11136kb

查看

[2024-08-28 11:21:57]
提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,M=6e5+5,S=2e4+5,inf=(ll)8e12,mo=998244353;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int cid,T;
int n,l[N],r[N],h[N],fa[N],dep[N];
int sz[N],hson[N],dfn[N],top[N],nw[N],cntp=0;
vector<int>e[N];
ll dp[N],f[N];
void dfs1(int x,int f){
    dep[x]=dep[f]+1,sz[x]=1;
    for(auto j:e[x]){
        dfs1(j,x);
        sz[x]+=sz[j];
        if(sz[j]>sz[hson[x]])hson[x]=j;
    }
}
void dfs2(int x,int topp){
    top[x]=topp,dfn[x]=++cntp,nw[cntp]=x;
    if(hson[x])dfs2(hson[x],topp);
    for(auto j:e[x]){
        if(j==hson[x])continue;
        dfs2(j,j);
    }
}
ll nres=0;
struct inter{
    map<int,int>itv;
    stack<pii>stk;
    int tagg[N];
    void modify(int x,int v){
        stk.push(mp(x,v));
        itv[x]+=v;
    }   
    vector<int>nwe;
    void erase(int v){
        map<int,int>::iterator it=itv.end();
        nwe.clear();
        while(it!=itv.begin()){
            it--;
            if(it->fir>=v){
                nwe.push_back(it->fir),stk.push(mp(it->fir,-(it->sec)));
                modify(v-1,it->sec);
            }
        }
        for(auto j:nwe)
            itv.erase(itv.find(j));
    }
    void clr(int x){
        while((int)stk.size()>tagg[x]){
            int pos=stk.top().fir,v=stk.top().sec;
            nres-=f[pos]*(ll)v%mo,itv[pos]-=v,nres=(nres+mo)%mo;
            stk.pop();
        }
    }
}H,L;
void dfs4(int x){
    int le=dep[x]-r[x],ri=dep[x]-l[x],upp=dep[x]-h[x];
    for(auto j:e[x])
        dfs4(j);
    L.modify(ri,1),L.modify(le-1,-1);
    //printf("%lld:%lld %lld %lld\n",x,le,ri,upp);
    L.erase(upp);
}
void solve_link(int x){
    //printf("!!!%lld:\n",x);
    int endp=x;
    while(hson[endp])
        endp=hson[endp];
    H.itv.clear();
    repp(i,dfn[endp],dfn[x]){
        H.tagg[i]=H.stk.size();
        int le=dep[nw[i]]-r[nw[i]],ri=dep[nw[i]]-l[nw[i]],upp=dep[nw[i]]-h[nw[i]];
        for(auto j:e[nw[i]]){
            if(j==hson[nw[i]])continue;
            L.itv.clear(),dfs4(j);
            for(auto nwm:L.itv)
                H.modify(nwm.fir,nwm.sec);
        }
        H.modify(ri,1),H.modify(le-1,-1);
        //printf("H%lld:%lld %lld %lld\n",nw[i],le,ri,upp);
        H.erase(upp);
    }
    nres=0;
    for(auto j:H.itv)
        if(j.fir>=0)nres+=f[j.fir]*(ll)j.sec,nres%=mo;//printf(",,,%lld %lld %lld\n",j.fir,j.sec,nres);
    rep(i,dfn[x],dfn[endp]){
        dp[nw[i]]+=nres;
        if(dep[nw[i]])f[dep[nw[i]]]=f[dep[nw[i-1]]];
        f[dep[nw[i]]]+=dp[nw[i]],f[dep[nw[i]]]%=mo;
        H.clr(i);
    }
    rep(i,dfn[x],dfn[endp])
        f[dep[nw[i]]]=0;
}
void dfs3(int x){
    if(top[x]==x&&x!=1)solve_link(x);
    else if(hson[1]==x)solve_link(x);
    if(x==1)dp[x]=1;
    if(dep[x])f[dep[x]]=f[dep[x]-1];
    f[dep[x]]+=dp[x],f[dep[x]]%=mo;
    if(hson[x])dfs3(hson[x]);
    for(auto j:e[x]){
        if(j==hson[x])continue;
        dfs3(j);
    }
    f[dep[x]]=0;
}
void solve(){
    read(n);
    rep(i,1,n)
        e[i].clear(),hson[i]=top[i]=dp[i]=f[i]=0;
    rep(i,2,n){
        read(fa[i]),read(l[i]),read(r[i]),read(h[i]);
        e[fa[i]].push_back(i);
    }
    dep[0]=-1,cntp=0;
    dfs1(1,0);
    dfs2(1,1);
    dfs3(1);
    rep(i,2,n)
        printf("%lld ",dp[i]);
    puts("");
}
signed main(){
    read(cid),read(T);
    while(T--)
        solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 0

Wrong Answer

time: 1ms

memory: 8112kb

input:

output:

result:

wrong answer 20th numbers differ - expected: '3', found: '2'

Pretest #2:

score: 0

Wrong Answer

time: 2ms

memory: 7932kb

input:

output:

19 18 35 1 38 15 50 0 0 15 349 261 0 507 195 0 108 472 0 0 103 614 375 0 814 0 360 607 174 989 6074 3053 139 1967 1200 1899 37 247 1200 3803 19 0 193 0 19 1117 34174 13503 45131 28491 17353 4360 11051 26873 0 25284 13050 6285 423 2642 21818 21818 15074 1200 7931 12746 0 17043 41694 169894 163823 9 0...

result:

wrong answer 14th numbers differ - expected: '525', found: '507'

Pretest #3:

score: 0

Wrong Answer

time: 0ms

memory: 7928kb

input:

output:

20 18 40 1 233 80 39 212 229 41 190 5094 56 0 4147 713 79 0 4129 5124 0 3313 2850 947 21534 9179 903 21496 2811 1 0 0 2811 143571 56660 67998 10105 25021 67687 3214 0 0 82668 44365 27652 38 25699 379349 23912 1787 84893 13400 25076 13513 0 3370 24657 0 24275 58446 49516 740 0 1198 48652 0 942 256 13...

result:

wrong answer 17th numbers differ - expected: '118', found: '79'

Pretest #4:

score: 0

Wrong Answer

time: 34ms

memory: 10996kb

input:

output:

1 1 28 83 25 29 108 111 1 79 21 0 29 21 133 133 533 381 1227 345 0 1112 352 21 423 108 236 20 3618 384 2884 2568 2114 0 7325 1427 7325 3531 1211 1211 19325 28 27101 28 25566 28 18010 0 4297 10182 0 104310 18494 85683 1003 13578 130166 229 28179 27681 117683 173543 113521 3918 9870 4030 1902 0 0 2142...

result:

wrong answer 232nd numbers differ - expected: '9107083', found: '5481709'

Pretest #5:

score: 0

Wrong Answer

time: 28ms

memory: 10736kb

input:

output:

2 35 2 2 34 3 34 2 35 277 514 1 0 444 1451 380 134 1106 1071 134 726 0 134 345 64 0 2177 232 69 0 29 1472 1695 0 1625 0 0 1589 0 4219 2460 104 68 725 1235 1303 14063 1171 0 15475 9322 1360 12697 20888 3645 2319 15348 4491 14009 7702 1339 6537 9758 9596 1339 25823 21514 4866 1338 36 4422 64 5226 325 ...

result:

wrong answer 4th numbers differ - expected: '3', found: '2'

Pretest #6:

score: 0

Time Limit Exceeded

input:

6
4
100000
1 1 1 0
2 1 1 0
3 1 1 0
4 2 2 0
5 1 1 0
6 2 2 0
7 6 6 0
8 3 3 0
9 6 6 0
10 8 8 0
11 6 6 0
12 12 12 0
13 11 11 0
14 2 2 0
15 2 2 0
16 2 2 0
17 9 9 0
18 1 1 0
19 4 4 0
20 18 18 0
21 13 13 0
22 20 20 0
23 3 3 0
24 21 21 0
25 8 8 0
26 11 11 0
27 11 11 0
28 3 3 0
29 21 21 0
30 1 1 0
31 27 27 0...

output:

result:

Pretest #7:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #8:

score: 0

Time Limit Exceeded

input:

8
4
100000
1 1 1 0
2 2 2 0
3 3 3 0
4 4 4 2
5 2 2 1
6 6 6 0
7 2 2 0
8 7 7 3
9 4 4 3
10 1 1 4
11 3 3 0
12 8 8 11
13 13 13 7
14 5 5 10
15 8 8 11
16 14 14 5
17 9 9 2
18 17 17 7
19 3 3 1
20 1 1 9
21 14 14 5
22 5 5 17
23 8 8 14
24 8 8 9
25 24 24 7
26 24 24 7
27 17 17 8
28 27 27 27
29 26 26 6
30 17 17 14
3...

output:

12 23 22 21 42 62 61 19 49 7 26 7 77 76 76 156 133 114 258 102 102 41 41 48 48 36 13 6 140 118 41 203 155 155 41 61 61 61 328 279 279 123 111 111 111 225 204 90 109 252 150 109 150 109 47 47 28 28 28 6 120 120 6 18 18 59 59 18 32 32 32 73 73 73 672 631 631 352 311 32 380 483 374 408 275 395 275 234 ...

result:

Pretest #9:

score: 0

Time Limit Exceeded

input:

output:

4 5 0 1 23 0 9 44 0 1 4 3 62 1 0 2 1 18 1 220 1 1 45 202 0 1 44 399 0 179 23 18 0 554 0 0 155 155 0 261 0 701 220 0 1214 971 23 417 269 155 148 0 779 0 85 40 62 756 62 554 1011 40 0 0 40 220 2408 18 0 0 0 2407 18 650 40 0 3381 502 2827 479 0 0 1613 62 0 62 18 1152 62 345 283 2428 628 1214 473 283 15...

result:

Pretest #10:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Pretest #12:

score: 0

Time Limit Exceeded

input:

12
4
100000
1 1 1 0
1 1 1 0
3 1 2 0
3 1 2 0
4 1 1 0
4 1 3 0
6 2 4 0
7 2 4 0
9 1 4 0
8 1 3 0
11 3 3 0
11 5 6 0
12 1 2 0
14 3 3 0
13 2 7 0
16 2 3 0
17 2 4 0
17 7 9 0
17 3 8 0
20 2 6 0
21 10 11 0
21 6 11 0
21 7 9 0
23 3 4 0
24 5 11 0
26 6 9 0
26 5 7 0
27 12 13 0
29 10 10 0
28 1 3 0
31 13 15 0
32 7 13 0...

output:

result:

Pretest #13:

score: 0

Time Limit Exceeded

input:

13
4
100000
1 1 1 0
2 1 2 0
3 2 2 2
4 2 4 1
5 1 2 4
6 4 6 2
7 1 6 4
8 6 6 5
9 5 8 8
10 6 6 1
11 8 11 5
12 8 11 1
13 4 8 6
14 4 7 1
15 11 15 5
16 1 1 10
17 6 9 7
18 8 16 2
19 2 9 10
20 6 20 7
21 12 14 11
22 9 14 14
23 6 7 22
24 12 14 11
25 20 20 21
26 10 20 0
27 19 26 8
28 21 23 12
29 4 13 23
30 15 2...

output:

28 55 26 109 25 246 162 79 24 1161 1052 1188 970 2125 699 480 1822 2880 993 4442 286 21 21 3699 298 9538 1352 622 189 189 1481 1505 15694 21512 834 834 5007 968 968 14494 725 23023 12855 17501 26963 26963 4370 55916 2673 2458 139790 114009 120206 117382 44163 44163 43673 53833 619 71600 8518 22800 2...

result:

Pretest #14:

score: 0

Time Limit Exceeded

input:

14
4
100000
1 1 1 0
2 1 1 1
1 1 1 0
2 1 2 1
4 2 2 1
5 2 2 1
7 1 4 1
8 2 5 3
8 5 5 3
10 2 3 5
11 1 6 5
10 1 4 5
12 5 8 1
12 3 6 5
13 3 6 2
15 2 5 8
17 6 7 6
18 6 8 5
17 10 10 1
18 4 5 5
20 4 11 7
22 8 9 4
23 9 13 12
24 9 13 10
24 6 8 7
26 3 13 13
26 11 14 11
28 11 11 2
27 9 16 8
30 6 12 0
31 13 17 16...

output:

38 0 2 37 1 150 149 39 34 33 109 0 226 69 374 32 300 333 407 0 406 329 30 225 629 371 225 34 2046 1345 255 1576 551 1826 576 0 2943 2943 14639 243 8257 1739 1414 6215 178 963 737 0 2057 0 19273 32354 1785 15629 30150 13806 1 16417 174 39 24 5516 70013 52465 90069 4377 550 914 70590 16513 5825 70557 ...

result:

Pretest #15:

score: 0

Time Limit Exceeded

input:

output:

8 69 0 2 998244352 1 56 1722 71 1 8 3 41 1651 0 33 1791 53172 1 201 51380 9 130 0 129 169280 0 0 139 1 68663 155580 56 65221 58336 56545 98965 104552 3443 97173 1651 0 0 92149 40769 1152205 3442 567214 217712 104552 56614 0 519084 35394 0 3442 1791 107925 546399 133884 0 5234 414601 1249835 0 3443 4...

result:

Pretest #16:

score: 0

Time Limit Exceeded

input:

output:

55 2 1 0 2 109 53 1 1 2061 1839 56 2 218 4394 2114 9812 2280 1 9648 57189 77088 0 4817 270 23743 2114 274 424 13930 165 218 9812 0 260 0 0 23413 272071 43 167449 0 268118 0 144363 42 153737 0 42833 132224 29121 16192 87118 13930 0 39 29645 164 28999 19460 121793 30920 4062 100494 75448 251009 48648 ...

result:

Pretest #17:

score: 0

Time Limit Exceeded

input:

output:

2 1 1 54 51 2 49 998244302 0 209 1 2 468 105 51 351 467 52 0 100 1 44 367 364 1 409 211 852 255 155 154 155 54 4355 154 0 4035 819 8854 3647 1610 1185 106 525 1728 3468 54 0 154 2710 1065 560 2187 714 9637 18397 2447 663 714 663 11376 9500 660 0 10716 51317 0 258 6703 0 15179 34143 10526 0 0 10471 1...

result:

Pretest #18:

score: 0

Time Limit Exceeded

input:

output:

60 2 64 1193 1 1132 3 10615 125 6733 1 61 4893 2023 12940 5964 2023 0 2022 0 14193 769 13000 5541 13586 4712 25741 7379 19674 998224396 646 646 0 19673 0 120670 23719 62476 100510 1132 0 2022 61 68484 8025 46728 1254 26001 9948 0 8695 15487 30512 15487 314245 8756 12940 30087 19311 8390 120310 0 130...

result:

Pretest #19:

score: 0

Time Limit Exceeded

input:

output:

38 1 37 873 5 1 37 15 982 41 39 21 868 1 86 22 1 2647 16 2646 712 1 3 675 3 947 637 859 29756 3 37 28887 6060 151 9044 20834 46025 20093 10653 84931 151238 8803 5448 141123 67827 9867 951 5 445 14246 8530 4843 8053 209482 4670 11606 10975 630 27222 5445 65552 0 7548 17107 18890 637 1931 15813 0 0 73...

result:

Pretest #20:

score: 0

Time Limit Exceeded

input:

output:

52 103 49 571 985 414 200 2 97 1658 97 155 1 106 200 45 157 2944 1994 157 311 2 576 204 1790 103 0 789 0 4348 5784 2962 52 346 2137 155 2253 4328 13652 9344 1201 103 41 297 53 6052 105 155 41 848 1114 3788 443 4374 2247 362 6809 791 457 757 0 457 757 14559 27642 13258 5640 951 0 0 457 394 14882 0 21...

result:

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 8140kb

input:

output:

result:

ok 20 numbers

Test #2:

score: 0

Wrong Answer

time: 2ms

memory: 8280kb

input:

output:

34 69 3 1 134 34 69 1 139 511 28 307 36 1 69 1410 169 1 1375 35 1 324 1410 1572 5078 139 3344 8060 35 1572 169 0 193 196 1 139 1 286 0 0 14675 3538 1607 89 6615 134 2981 19649 0 0 28 11596 8615 20 290 0 28 44058 16085 31586 19429 159649 8060 10321 62151 5795 30389 71949 7536 2813 61245 375 7891 6108...

result:

wrong answer 5th numbers differ - expected: '236', found: '134'

Test #3:

score: 0

Wrong Answer

time: 2ms

memory: 7932kb

input:

output:

25 249 447 129 26 274 207 1 16 0 78 1288 26 275 25 52 17 763 1 507 3700 129 3253 825 2514 413 3253 0 6382 19019 20093 9716 823 3914 2067 9277 585 8365 79274 36681 2789 274 274 22165 72494 0 53117 0 2789 296500 0 41180 134866 6759 0 6759 1288 46560 278623 56757 700249 195711 80845 3914 37444 36895 20...

result:

wrong answer 7th numbers differ - expected: '929', found: '207'

Test #4:

score: 0

Wrong Answer

time: 32ms

memory: 9380kb

input:

output:

3 2 1 0 41 1 40 0 118 117 207 34 42 81 166 250 33 33 2 41 82 33 3342 235 42 3124 221 0 0 2837 121 99 6180 2342 40 1974 6140 375 1839 37806 0 17745 22073 1315 5604 0 13643 4340 5637 548 0 0 5362 548 33 548 106 8770 0 40 158 0 4979 4979 0 14027 0 19676 8884 2837 160 375 2 79738 375 384 14548 7082 6874...

result:

wrong answer 4th numbers differ - expected: '2', found: '0'

Test #5:

score: 0

Wrong Answer

time: 32ms

memory: 11136kb

input:

output:

34 33 0 6 65 0 5 1 4 32 12 7 6 0 265 0 264 998244285 16 229 95 35 223 362 1 1017 1 26 5427 3593 823 2835 878 132 2209 1314 588 24 1550 429 24 7761 264 0 24 1068 837 0 495 1018 8258 430 194 229 34 7967 324 21377 229 14847 1266 0 583 5055 547 0 45349 4362 6902 90 693 16835 10064 693 54761 4611 37001 1...

result:

wrong answer 11th numbers differ - expected: '14', found: '12'

Test #6:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #7:

score: 0

Time Limit Exceeded

input:

7
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 0
5 2 2 0
5 2 2 0
7 1 1 0
8 1 1 0
6 1 1 0
7 3 3 0
9 3 3 0
12 2 2 0
10 2 2 0
13 1 1 0
13 4 4 0
13 7 7 0
15 1 1 0
15 7 7 0
16 7 7 0
19 1 1 0
18 8 8 0
19 2 2 0
23 1 1 0
23 5 5 0
24 8 8 0
23 6 6 0
27 3 3 0
28 4 4 0
26 12 12 0
29 6 6 0
30 1 1 0
31 12 12 0
30 9 9 0...

output:

result:

Test #8:

score: 0

Time Limit Exceeded

input:

8
4
100000
1 1 1 0
2 2 2 0
3 2 2 1
4 2 2 2
5 3 3 0
6 6 6 2
7 1 1 6
8 8 8 2
9 1 1 6
10 2 2 3
11 4 4 2
12 6 6 5
13 2 2 11
14 1 1 6
15 7 7 4
16 7 7 3
17 14 14 15
18 12 12 12
19 17 17 3
20 20 20 11
21 5 5 7
22 12 12 3
23 14 14 10
24 3 3 1
25 23 23 10
26 5 5 18
27 5 5 25
28 18 18 1
29 2 2 14
30 23 23 3
3...

output:

7 13 12 5 18 5 4 25 24 29 33 29 24 24 73 48 24 50 50 37 89 89 60 125 36 23 23 68 39 39 35 23 23 52 52 45 38 14 9 9 9 9 9 9 9 42 9 67 44 9 2 11 2 2 106 106 106 106 174 167 99 92 126 97 145 165 158 90 239 189 180 143 143 114 90 90 279 90 203 322 313 261 237 223 134 90 90 233 90 90 90 90 163 154 131 94...

result:

Test #9:

score: 0

Time Limit Exceeded

input:

9
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
3 1 1 0
4 2 2 1
6 2 2 2
6 1 1 2
8 3 3 2
9 1 1 4
8 4 4 0
9 4 4 0
12 6 6 3
13 3 3 4
13 6 6 3
15 5 5 0
15 2 2 7
15 4 4 2
17 5 5 2
18 5 5 0
18 4 4 6
19 2 2 8
22 8 8 9
23 3 3 10
24 6 6 12
25 7 7 13
24 1 1 11
27 3 3 7
27 12 12 2
28 4 4 0
30 3 3 9
31 15 15 15
32 1 1 7
31 ...

output:

1 1 15 0 14 0 13 57 0 1 42 27 0 39 13 11 114 83 57 0 26 26 26 0 0 26 26 14 52 26 26 26 0 11 15 0 11 68 11 11 78 26 11 11 0 230 0 0 203 203 0 998243668 203 189 0 39 189 137 0 52 241 0 0 252 199 188 26 188 52 0 110 26 110 110 95 0 57 22 27 11 11 27 166 11 155 0 344 0 138 39 0 116 115 22 0 314 115 198 ...

result:

Test #10:

score: 0

Time Limit Exceeded

input:

10
4
100000
1 1 1 0
2 1 1 0
3 3 3 0
4 3 4 0
5 3 5 0
6 1 4 0
7 5 5 0
8 5 7 0
9 3 6 0
10 6 10 0
11 1 2 0
12 8 11 0
13 4 12 0
14 2 12 0
15 7 10 0
16 6 8 0
17 13 15 0
18 8 9 0
19 2 6 0
20 8 14 0
21 3 18 0
22 11 18 0
23 5 11 0
24 6 12 0
25 3 24 0
26 13 23 0
27 3 8 0
28 14 22 0
29 4 26 0
30 1 5 0
31 13 17...

output:

result:

Test #11:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #12:

score: 0

Time Limit Exceeded

input:

output:

result:

Test #13:

score: 0

Time Limit Exceeded

input:

13
4
100000
1 1 1 0
2 1 2 1
3 1 2 2
4 1 3 2
5 1 5 4
6 1 4 4
7 6 6 1
8 3 7 5
9 3 4 4
10 5 6 2
11 6 9 4
12 5 11 9
13 1 3 4
14 6 10 10
15 4 6 8
16 3 8 6
17 1 9 3
18 3 13 8
19 3 11 10
20 2 4 11
21 12 13 0
22 13 17 20
23 9 17 1
24 10 11 16
25 22 25 9
26 5 9 4
27 12 27 26
28 13 13 22
29 8 23 1
30 21 23 19...

output:

25 24 23 48 23 122 194 169 239 285 214 96 47 47 192 1948 2182 1132 385 216 455 47 1507 94 94 4391 21 779 13861 5938 14206 13992 4449 22496 12875 3304 3304 13811 13690 9811 3933 619 619 5401 13977 106342 3918 13555 35871 2821 276664 275227 172324 207717 203165 270061 269845 1838 68391 19507 19507 134...

result:

Test #14:

score: 0

Time Limit Exceeded

input:

output:

1 1 68 67 2 0 2 1 1 337 67 1 136 200 539 0 131 0 0 67 131 0 0 136 135 1009 1939 1340 0 537 1750 62 136 6321 0 6059 1212 61 799 2935 1 67 995 61 0 2686 2671 0 462 0 15247 34022 12060 15315 53483 131 0 106761 672 67383 0 2805 15046 106357 537 604 0 15899 13496 227416 15720 7604 0 404 3407 188917 1199 ...

result:

Test #15:

score: 0

Time Limit Exceeded

input:

output:

3 5 6 46 3 4 93 44 11 310 47 46 92 6 220 0 2 2 440 40 5 40 1 400 3608 0 0 269 620 2369 90 665 1614 1614 354 0 44 993 993 0 4971 7101 12224 10238 3493 3493 1331 10105 5850 6497 811 4749 891 764 3648 4680 3540 47 42515 21825 22926 24828 14491 0 8732 0 1052 5286 538 538 80860 2 95706 47 22835 2 42677 6...

result:

Test #16:

score: 0

Time Limit Exceeded

input:

output:

1 1 2 60 3 355 1 2 0 4 1360 3551 2 3550 2 1828 64 62 998244296 5 52 351 12001 1 355 24797 3595 20363 17 19393 831 21 0 3603 89801 126823 19 94 86 48 125463 19208 0 0 121859 109194 28255 12352 60752 9464 4208 37201 61167 85785 2433 0 205716 134890 36798 45041 96474 76554 16268 255816 45041 61 81610 4...

result:

Test #17:

score: 0

Time Limit Exceeded

input:

output:

4 54 4 4 3 15 53 27 1 8 19 159 5 1 316 1 159 0 0 50 0 48 528 899 364 316 510 0 316 48 371 626 1 262 898 108 1651 1111 0 1214 1341 790 1555 1160 1500 1865 1816 54 0 633 524 1500 680 3520 528 2860 1956 478 212 1548 1257 44 212 729 0 3366 6322 1555 212 3535 2767 1576 0 0 11442 6553 11443 792 2128 43 49...

result:

Test #18:

score: 0

Time Limit Exceeded

input:

18
4
100000
1 1 1 0
1 1 1 0
3 1 2 1
2 1 2 0
2 2 2 0
5 1 3 1
6 1 1 1
6 2 3 2
6 1 3 2
9 1 4 1
10 2 3 1
12 1 3 0
10 1 4 2
11 2 5 0
12 4 5 1
14 2 4 1
15 5 6 2
16 4 5 5
18 3 3 5
18 1 6 4
18 3 4 4
21 2 4 3
21 4 7 4
23 7 9 3
23 1 5 3
25 3 5 3
26 5 6 2
25 1 7 4
29 3 4 6
30 4 11 2
29 1 3 3
29 1 5 6
32 9 12 0...

output:

47 2 1 96 44 48 0 40 3 2679 183 230 95 2627 48 94 2495 0 0 2447 0 37572 131 40043 10612 5122 5306 37324 2810 47951 39005 47 125490 66026 47 125358 18075 84 125227 12546 275399 0 45141 288291 2811 275191 2811 1 253038 16715 89388 7570 1441 1 8064 1394 87995 227539 0 1149686 2811 230389 1639348 230258...

result:

Test #19:

score: 0

Time Limit Exceeded

input:

output:

3 1 43 1 1 0 515 559 0 1 427 1 515 998243752 1884 998243797 942 898 998243195 340 9674 2015 1073 1884 7614 1971 942 3758 3978 1108 10912 11854 164 2 28792 25939 558 4787 559 34661 33 2870 1 8345 34330 26865 43 0 13064 898 43 10283 898 21266 10283 0 0 0 173992 59346 52399 23097 106078 26438 17548 124...

result:

Test #20:

score: 0

Time Limit Exceeded

input:

output:

1 44 2 43 43 1 42 1 41 172 85 87 0 41 172 816 45 170 1071 88 814 0 345 83 0 1228 41 1015 10341 2309 424 4950 816 2206 1063 3763 3241 3634 2299 1284 2520 0 2181 0 0 168 0 168 25351 17570 7768 0 2756 5587 168 42 548 0 1863 45431 61497 0 32997 25977 0 0 2767 126 51684 116 1928 23255 116 10375 18821 557...