QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#503267#9159. 登山hansiyuan#35 272ms108496kbC++143.8kb2024-08-03 17:19:422024-08-03 17:19:48

Judging History

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

  • [2024-08-03 17:19:48]
  • 评测
  • 测评结果:35
  • 用时:272ms
  • 内存:108496kb
  • [2024-08-03 17:19:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
namespace solve1{
    const int N=5005;
    int n;
    vector<int> G[N];
    int fa[N],l[N],r[N],d[N];
    int f[N],g[N][N];
    void dfs1(int u){
        int k=1,zu=fa[u];
        while(zu){
            if(k>d[u] && l[u]<=k && k<=r[u]) g[u][zu]++;
            k++; zu=fa[zu];
        }
        for(int v:G[u]){
            dfs1(v);
            int k=1,zu=fa[u];
            while(zu){
                if(k>d[u])
                    g[u][zu] = (g[u][zu]+g[v][zu])%mod;
                k++; zu=fa[zu];
            }
        }
    }
    void main(){
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++) G[i].clear();
        scanf("%d",&n);
        for(int i=2;i<=n;i++){
            scanf("%d%d%d%d",&fa[i],&l[i],&r[i],&d[i]);
            G[fa[i]].push_back(i);
        }
        dfs1(1);
        f[1] = 1;
        for(int u=2;u<=n;u++){
            int zu=fa[u];
            while(zu){
                f[u] = (f[u] + 1ll*f[zu]*g[u][zu]%mod) %mod;
                zu = fa[zu];
            }
            printf("%d ",f[u]);
        }
        puts("");
    }
}
namespace solve2{
    const int N=1e5+5;
    int n;
    vector<int> G[N],G1[N];
    int fa[N][20],l[N],r[N],d[N];
    int dep[N],siz[N],son[N],dfn[N],top[N],tim;
    int f[N];
    int tr[N];
    void add(int i,int x){
        for(;i<=n;i+=i&-i) tr[i] = (tr[i]+x)%mod;
    }
    int ask(int i){
        int res=0;
        for(;i;i-=i&-i) res = (res+tr[i])%mod;
        return res;
    }
    void update(int u,int zu,int val){
        while(top[u] != top[zu]){
            add(dfn[top[u]],val);
            add(dfn[u]+1,-val);
            u = fa[top[u]][0];
        }
        add(dfn[zu],val);
        add(dfn[u]+1,-val);
    }
    void dfs0(int u){
        siz[u] = 1;
        for(int v:G[u]){
            dep[v] = dep[u]+1;
            for(int i=1;i<=18;i++)
                fa[v][i] = fa[fa[v][i-1]][i-1];
            dfs0(v);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
    void dfs1(int u,int tp){
        dfn[u] = ++tim;
        top[u] = tp;
        if(son[u]) dfs1(son[u],tp);
        for(int v:G[u]){
            if(v==son[u]) continue;
            dfs1(v,v);
        }
    }
    void dfs2(int u){
        if(u==1) f[u]=1;
        else f[u]=ask(dfn[u]);
        for(int v:G1[u]){
            update(v,u,f[u]);
        }
        for(int v:G[u])
            dfs2(v);
    }
    int get_fa(int u,int k){
        for(int i=18;i>=0;i--){
            if(k>=(1<<i))
                u=fa[u][i], k-=(1<<i);
        }
        return u;
    }
    void main(){
        tim = 0;
        for(int i=1;i<=n;i++) G[i].clear(),G1[i].clear();
        memset(siz,0,sizeof(siz));
        memset(son,0,sizeof(son));
        memset(tr,0,sizeof(tr));
        scanf("%d",&n);
        for(int i=2;i<=n;i++){
            scanf("%d%d%d%d",&fa[i][0],&l[i],&r[i],&d[i]);
            G[fa[i][0]].push_back(i);
        }
        dep[1]=1; dfs0(1);
        dfs1(1,1);
        for(int u=2;u<=n;u++){
            int zu = get_fa(u,l[u]);
            int k=l[u];
            while(k<=r[u]){
                if(k>d[u]) G1[zu].push_back(u);
                zu = fa[zu][0];
                k++;
            }
        }
        dfs2(1);
        for(int i=2;i<=n;i++)
            printf("%d ",(f[i]+mod)%mod);
        puts("");
    }
}
int main(){
	// freopen("ex_3.in","r",stdin);
    // freopen("my.out","w",stdout);
    int tid,T;
    scanf("%d",&tid);
    scanf("%d",&T);
    while(T--){
       // solve2::main();
        if(tid<=5) solve1::main();
        else solve2::main();
    }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 5
Accepted
time: 34ms
memory: 107040kb

input:

1
4
6
1 1 1 0
1 1 1 0
3 1 2 1
3 2 2 0
4 2 3 1
6
1 1 1 0
2 1 2 0
2 1 2 0
1 1 1 0
4 1 2 2
6
1 1 1 0
1 1 1 0
3 1 2 1
4 2 2 0
3 1 1 0
6
1 1 1 0
1 1 1 0
3 1 1 0
4 2 3 1
2 1 2 0

output:

1 4 2 1 5 
3 4 4 1 0 
1 2 1 2 2 
2 2 5 3 3 

result:

ok 20 numbers

Pretest #2:

score: 5
Accepted
time: 35ms
memory: 107172kb

input:

2
4
300
1 1 1 0
2 1 2 1
3 1 3 1
1 1 1 0
3 1 3 0
4 2 2 3
7 1 2 0
8 2 2 2
7 1 3 4
7 3 4 4
11 1 6 1
12 1 3 5
10 2 5 5
13 1 5 4
13 4 7 2
15 8 8 8
16 8 9 4
15 1 9 6
18 4 5 6
19 3 8 8
18 5 10 2
19 3 7 5
23 5 7 6
22 6 8 10
23 4 7 3
24 1 4 6
24 8 12 9
28 7 11 8
26 1 9 7
28 1 3 1
29 2 5 0
32 1 6 4
30 5 12 7
...

output:

19 18 35 1 38 15 50 0 0 15 349 261 0 525 195 0 108 490 0 0 103 632 393 0 814 0 378 625 174 1025 6236 3125 139 2003 1218 1935 37 265 1218 3929 19 0 211 0 19 1135 35695 14466 46868 29814 18352 5053 11375 28739 0 27114 13392 7593 423 2714 22394 22394 15506 1218 8147 13088 0 17493 42846 178996 171635 9 ...

result:

ok 1196 numbers

Pretest #3:

score: 5
Accepted
time: 27ms
memory: 107868kb

input:

3
4
300
1 1 1 0
2 1 2 1
3 3 3 0
2 1 2 1
3 1 3 1
3 1 3 0
4 1 4 1
6 4 4 2
9 3 5 1
7 3 4 2
10 2 5 4
12 1 5 2
11 1 3 2
12 3 6 6
13 6 6 3
13 3 8 0
14 3 5 0
16 3 5 5
16 6 9 5
20 2 7 3
20 3 7 9
21 7 9 2
23 3 4 8
21 4 9 6
24 11 12 2
25 3 4 1
27 7 13 5
26 1 8 3
29 2 4 6
29 6 15 14
29 5 5 10
32 6 10 11
30 1 9...

output:

20 18 40 1 233 80 39 212 229 41 190 5094 56 0 4147 713 118 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 1...

result:

ok 1196 numbers

Pretest #4:

score: 5
Accepted
time: 193ms
memory: 108212kb

input:

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

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:

ok 19996 numbers

Pretest #5:

score: 5
Accepted
time: 196ms
memory: 107072kb

input:

5
4
5000
1 1 1 0
1 1 1 0
1 1 1 0
2 1 2 0
3 1 1 1
4 1 1 0
6 1 3 2
7 1 3 1
8 2 2 0
8 1 3 2
11 3 5 1
10 1 5 4
13 1 2 4
12 3 4 3
15 3 5 2
15 2 6 2
15 1 3 3
16 7 7 3
19 1 7 4
18 2 3 4
20 1 10 5
21 2 3 8
21 4 9 6
22 7 9 3
24 2 6 8
25 1 3 4
25 3 4 1
26 3 4 3
29 5 11 9
28 8 11 12
29 7 9 11
32 5 12 5
32 11 1...

output:

2 35 2 3 34 5 34 3 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 1337 15332 1171 0 16744 9322 1360 13966 22157 3645 2319 16617 4491 15278 7736 1339 7806 9758 10865 1339 28395 22817 4866 1338 36 4422 64 5226 325...

result:

ok 19996 numbers

Pretest #6:

score: 5
Accepted
time: 219ms
memory: 34984kb

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:

7 90 1343 13340 200010 2186770 17480820 279693113 800242414 420706509 214087588 358274752 946289212 530647994 955227776 663050301 438245147 621009062 780623708 80919478 728275212 743623748 978006196 735181462 256088384 612217572 335562169 696082683 110948988 53450390 637356472 107616671 988788196 54...

result:

ok 399996 numbers

Pretest #7:

score: 5
Accepted
time: 272ms
memory: 31784kb

input:

7
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
3 1 1 0
1 1 1 0
3 1 1 0
7 1 1 0
6 1 1 0
9 2 2 0
6 1 1 0
6 1 1 0
7 2 2 0
9 2 2 0
11 1 1 0
11 2 2 0
14 4 4 0
12 1 1 0
16 3 3 0
15 1 1 0
17 3 3 0
20 5 5 0
18 4 4 0
20 2 2 0
19 2 2 0
22 5 5 0
22 2 2 0
22 3 3 0
23 5 5 0
27 7 7 0
26 6 6 0
27 5 5 0
31 1 1 0
33 9 9 0
34 2 ...

output:

1 1 1 1 31 2 2 94 31 1298 33 1 126 41443 62 95 35 93 1490650 94 49108564 2 41443 62 31502098 1491949 41443 1 1 882058713 1298 808538694 650336433 808538694 808538695 53283330 1298 31502098 1 31502098 319947267 692436002 360370658 1534689 1298 41443 692394559 41443 518136386 1298 972986764 32 6923530...

result:

ok 399996 numbers

Pretest #8:

score: 0
Wrong Answer
time: 213ms
memory: 34860kb

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 119 951 10460 94139 846300 9309299 46452356 510975904 118443136 541516415 919006444 285103172 854543013 136036313 226082464 490418279 847345227 638396560 446965785 238340219 377604185 403704606 256938113 543384325 354097176 836288583 582399410 832772335 5411294 745608945 721014387 242725252 21538...

result:

wrong answer 2nd numbers differ - expected: '23', found: '119'

Pretest #9:

score: 0
Wrong Answer
time: 238ms
memory: 29088kb

input:

9
4
100000
1 1 1 0
2 2 2 0
2 1 1 1
2 2 2 1
1 1 1 0
6 1 1 1
3 1 1 0
6 1 1 0
7 1 1 2
6 2 2 0
8 3 3 2
9 1 1 1
9 1 1 0
12 5 5 2
14 1 1 3
13 4 4 3
13 1 1 3
14 3 3 3
17 5 5 2
19 1 1 0
18 3 3 3
22 3 3 5
23 1 1 0
21 5 5 3
22 4 4 4
23 7 7 2
24 6 6 3
25 2 2 1
29 6 6 7
29 8 8 3
31 8 8 7
32 6 6 5
31 5 5 7
31 2 ...

output:

4 6 0 1 23 0 11 642 0 1 5 645 16666 1 0 2 643 582668 1 16897372 643 643 1285 455646376 0 1 642 323519893 0 436349696 582691 582668 0 53016786 0 0 3655404 113317524 0 814836031 0 691627616 16897372 0 453467457 521720025 23 920660209 508663827 3655404 387641940 0 508663185 0 16689 600430150 16666 5086...

result:

wrong answer 8th numbers differ - expected: '44', found: '642'

Pretest #10:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Pretest #11:

score: 0
Time Limit Exceeded

input:

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

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:


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:


result:


Pretest #15:

score: 0
Time Limit Exceeded

input:

15
4
100000
1 1 1 0
1 1 1 0
3 1 1 1
3 2 2 0
4 1 2 0
5 1 1 2
2 1 2 0
3 1 2 0
7 3 3 1
9 3 3 1
8 1 2 1
10 1 5 1
8 2 3 0
9 1 2 1
11 3 3 3
14 1 2 2
15 1 3 1
15 2 4 0
15 1 4 3
17 3 4 2
19 5 5 2
21 4 6 4
21 6 6 2
24 2 4 6
24 3 7 4
22 3 4 0
23 1 5 5
23 5 6 6
26 2 8 3
30 5 9 8
27 4 6 1
27 3 7 2
31 6 8 7
32 5...

output:


result:


Pretest #16:

score: 0
Time Limit Exceeded

input:

16
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
4 1 1 1
1 1 1 0
2 1 2 0
7 2 3 2
3 2 2 0
6 2 2 0
8 2 3 0
11 1 5 1
11 2 5 3
11 3 3 4
14 2 6 2
14 2 3 0
12 2 3 0
12 4 5 0
16 3 7 1
19 3 7 2
18 3 4 2
21 2 4 0
22 1 3 0
21 1 6 6
21 4 5 3
21 1 7 4
23 1 10 2
26 1 6 4
23 9 10 0
25 7 8 1
25 3 9 2
27 9 11 3
29 4 11 7
33 2 6...

output:


result:


Pretest #17:

score: 0
Time Limit Exceeded

input:

17
4
100000
1 1 1 0
2 2 2 0
1 1 1 0
1 1 1 0
5 1 2 1
5 1 2 1
6 2 2 2
7 1 1 0
8 1 1 3
8 3 4 2
6 1 3 2
9 2 4 1
8 4 4 0
11 1 4 2
10 3 3 1
11 2 5 0
14 2 3 0
17 4 4 2
14 3 4 4
17 1 4 2
19 2 6 6
17 1 1 5
18 1 5 3
23 3 7 2
22 2 3 7
24 4 6 3
23 1 7 4
23 7 7 5
27 5 6 2
26 6 9 5
28 1 7 4
30 1 9 5
29 2 6 6
29 4...

output:


result:


Pretest #18:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Pretest #19:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Pretest #20:

score: 0
Time Limit Exceeded

input:

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

output:


result:



Final Tests

Test #1:

score: 5
Accepted
time: 30ms
memory: 108416kb

input:

1
4
6
1 1 1 0
2 1 2 0
3 2 3 0
3 2 2 2
5 4 4 3
6
1 1 1 0
1 1 1 0
3 1 1 1
3 1 1 0
4 2 3 1
6
1 1 1 0
2 1 2 1
2 1 2 0
2 2 2 0
2 1 2 0
6
1 1 1 0
2 1 1 1
1 1 1 0
4 1 2 1
5 1 2 2

output:

4 11 5 1 1 
1 2 1 2 3 
5 1 6 1 6 
1 0 2 1 0 

result:

ok 20 numbers

Test #2:

score: 5
Accepted
time: 29ms
memory: 108108kb

input:

2
4
300
1 1 1 0
2 1 1 0
1 1 1 0
4 1 2 1
2 2 2 0
6 1 2 1
3 1 3 0
4 1 2 1
6 1 1 1
10 2 3 0
6 2 3 2
11 2 4 0
11 4 5 2
14 4 4 5
10 1 3 2
12 3 4 0
12 2 4 1
15 7 7 5
17 3 4 1
16 4 4 0
21 2 2 5
20 2 4 2
20 2 2 1
23 3 5 1
20 3 4 0
22 4 5 0
26 5 7 1
28 1 8 1
27 2 6 6
26 1 5 2
30 1 3 6
28 1 1 4
28 2 7 6
34 2 ...

output:

34 69 3 1 236 34 104 1 173 749 28 443 36 1 69 2124 271 1 2089 35 1 528 2124 2388 7628 444 4976 12140 35 2388 271 0 193 298 1 444 1 388 0 0 22121 5170 2423 89 9981 236 4511 29441 0 0 28 17308 12797 20 290 0 28 66702 24245 47192 29221 238597 12140 15625 92547 8753 45281 107649 11412 4241 91539 477 118...

result:

ok 1196 numbers

Test #3:

score: 5
Accepted
time: 31ms
memory: 108496kb

input:

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

output:

25 249 447 129 26 274 929 1 16 0 78 1288 26 275 25 52 17 763 1 1951 3700 851 3253 825 2514 1857 3253 0 6382 19019 20093 9716 823 3914 2067 9277 585 8365 79274 36681 2789 274 274 22165 72494 0 53117 0 2789 300999 0 41180 139365 6759 0 6759 1288 46560 278623 56757 709247 195711 80845 3914 37444 36895 ...

result:

ok 1196 numbers

Test #4:

score: 5
Accepted
time: 171ms
memory: 108476kb

input:

4
4
5000
1 1 1 0
2 1 2 1
1 1 1 0
4 1 1 0
1 1 1 0
3 2 3 2
6 1 2 1
5 1 2 0
8 3 3 1
10 1 3 2
8 2 2 0
11 1 5 4
11 3 5 3
13 4 5 3
12 3 3 1
16 1 5 1
13 4 5 5
18 1 5 5
17 1 6 5
17 1 5 4
20 5 7 4
19 1 1 7
23 1 8 3
23 4 6 4
23 8 9 7
24 3 4 2
27 3 6 3
28 5 8 9
26 1 4 4
27 3 10 8
28 8 11 9
31 4 6 3
31 10 10 2
...

output:

3 2 1 2 41 1 40 3 118 117 207 34 42 81 166 332 33 33 2 41 82 33 3462 235 42 3244 221 0 0 2957 121 99 6338 2342 40 1974 6298 375 11832 39000 0 18301 22749 1315 5762 0 14123 4460 5795 548 0 0 5520 548 33 548 106 9048 0 40 158 0 5137 5137 0 14387 0 30149 9193 2957 160 375 2 82113 375 384 14939 7233 711...

result:

ok 19996 numbers

Test #5:

score: 5
Accepted
time: 168ms
memory: 107220kb

input:

5
4
5000
1 1 1 0
2 2 2 1
3 1 2 2
1 1 1 0
3 1 1 0
4 2 2 3
5 1 1 1
8 3 3 1
8 2 3 2
6 4 4 3
10 2 4 2
10 2 4 2
12 4 5 3
11 2 3 4
11 5 5 1
14 1 3 5
16 1 1 2
15 1 3 0
17 1 4 2
18 3 7 3
21 5 8 6
18 6 7 2
22 1 5 5
24 4 7 4
21 5 7 7
24 2 9 0
26 9 9 2
24 5 9 9
29 8 11 2
30 3 7 4
30 8 9 6
31 5 10 6
30 3 5 4
34...

output:

34 33 0 6 65 0 5 1 4 32 14 7 7 0 265 0 264 97 18 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 10523 58...

result:

ok 19996 numbers

Test #6:

score: 5
Accepted
time: 220ms
memory: 35580kb

input:

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

output:

13 116 1159 11577 150385 1654119 16540031 198480359 787928493 734581969 103223677 120676063 963754385 618704320 378636756 206516872 241703175 693677871 68103114 817225791 671888130 60162705 601476665 456558188 30918290 836035627 422508580 961059777 721412290 780076554 866081801 542037914 961741065 6...

result:

ok 399996 numbers

Test #7:

score: 5
Accepted
time: 246ms
memory: 29856kb

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:

1 1 1 21 1 376 9022 162020 2 1 3879458 77588784 1 475771479 9043 1 475771500 836010287 21 836010287 21 723456114 723627157 3879458 171043 462547233 193433576 974019581 162021 821331611 162021 376 162020 686601685 418942555 31199510 217891022 462547233 836010287 944144826 217891022 575663750 44315401...

result:

ok 399996 numbers

Test #8:

score: 0
Wrong Answer
time: 207ms
memory: 34832kb

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 97 1163 6971 104565 418163 4181629 66906064 669060639 690447061 374262385 244903975 207228906 659586895 962788311 399497659 730680551 391105894 566179223 536456275 448009181 39105217 503323377 388000521 493749071 450764130 63899758 511198064 452707942 719758946 925456306 51998579 519985790 2086361...

result:

wrong answer 2nd numbers differ - expected: '13', found: '97'

Test #9:

score: 0
Wrong Answer
time: 241ms
memory: 31328kb

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 1 404 0 4039 68662 0 1 1441887 18744516 0 412379351 4039 608462120 137324 142732623 68662 0 429897223 320542320 137455355 0 0 890073749 698441054 404 994944422 628203068 215087839 722458359 0 854431840 15 0 981357877 728060737 973830201 534375465 317242389 320542320 211519731 608462120 0 5199...

result:

wrong answer 5th numbers differ - expected: '14', found: '404'

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:

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

output:


result:


Test #12:

score: 0
Time Limit Exceeded

input:

12
4
100000
1 1 1 0
2 1 2 0
3 2 3 0
4 1 3 0
2 1 1 0
4 2 2 0
3 1 2 0
8 1 4 0
8 1 3 0
5 2 5 0
9 1 4 0
10 3 5 0
11 1 6 0
11 3 6 0
11 3 3 0
14 2 6 0
17 3 7 0
14 2 4 0
14 4 6 0
18 2 8 0
18 6 9 0
21 8 10 0
22 5 5 0
20 6 8 0
22 1 4 0
24 3 9 0
26 3 8 0
25 3 3 0
24 6 7 0
25 5 9 0
27 2 9 0
32 4 6 0
32 9 11 0
...

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:


result:


Test #14:

score: 0
Time Limit Exceeded

input:

14
4
100000
1 1 1 0
1 1 1 0
1 1 1 0
4 1 2 1
1 1 1 0
5 1 1 2
6 1 1 0
6 2 2 1
5 2 3 2
5 1 2 1
7 2 2 1
8 1 2 1
11 2 4 1
11 4 4 2
15 2 4 0
13 1 3 3
15 1 3 3
18 2 4 4
16 2 5 5
16 4 4 0
18 6 6 4
22 4 4 5
18 2 5 5
20 5 6 5
24 1 6 4
25 5 6 2
22 3 4 1
28 3 7 0
25 2 4 4
29 1 6 4
27 3 8 0
28 5 5 7
30 2 3 1
33 ...

output:


result:


Test #15:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

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

output:


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:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

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

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

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

output:


result: