QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#502828#9159. 登山Tx_Lcy#0 430ms70188kbC++145.4kb2024-08-03 14:56:392024-08-03 14:56:39

Judging History

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

  • [2024-08-03 14:56:39]
  • 评测
  • 测评结果：0
  • 用时：430ms
  • 内存：70188kb
查看
  • [2024-08-03 14:56:39]
  • 提交

answer

//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=1e5+10;
int const mod=998244353;
int n,l[N],r[N],Fa[N],h[N];
vector<int>a[N];
#define add(x,y) (x=(x+y)%mod)
namespace BF{
    int const N=5e3+10;
    int Sum,mini[N],kth[N][N],dp[N],sm[N],dep[N];
    inline void dfs(int x,int fa){
        dep[x]=dep[fa]+1,kth[x][dep[x]]=x;
        rep(i,1,dep[x]-1) kth[x][i]=kth[fa][i];
        for (auto v:a[x]) dfs(v,x);
    }
    inline void getdp(int x,int Min){
        Min=min(Min,mini[x]);
        int liml=dep[x]-r[x],limr=dep[x]-l[x];
        limr=min(limr,Min);
        if (x!=1 && liml<=limr)
            add(Sum,(sm[kth[x][limr]]+mod-sm[kth[x][liml-1]])%mod);
        for (auto v:a[x]) getdp(v,Min);
    }
    inline void Dfs(int x,int fa){
        if (x!=1) Sum=0,getdp(x,mini[x]),dp[x]=Sum;
        sm[x]=sm[Fa[x]],add(sm[x],dp[x]);
        for (auto v:a[x]) Dfs(v,x);
    }
    inline void work(){
        rep(i,1,n) dp[i]=sm[i]=0;
        dp[1]=1;
        rep(i,1,n) sm[i]=1;
        dfs(1,0);
        rep(i,1,n) mini[i]=dep[i]-h[i]-1;
        Dfs(1,0);
        rep(i,2,n) cout<<dp[i]<<' ';
        cout<<'\n';
    }
}
namespace Sub1{
    int Sum,id1[N],id2[N],fa[20][N],dp[N],rev[N],siz[N],heavy[N],dep[N],dfn[N],L[N],R[N];
    struct Tree_Array{
        int c[N];
        #define lowbit(x) (x&(-x))
        inline void update(int x,int v){while (x<N) c[x]+=v,c[x]%=mod,x+=lowbit(x);}
        inline int query(int x){int R=0;while (x) R+=c[x],R%=mod,x-=lowbit(x);return R;}
    }T,T2,T3;
    int answer[N];
    vector< pair<int,int> >qrys[N];
    inline int kth(int x,int y){
        per(i,19,0)
            if (y>>i&1) x=fa[i][x];
        return x;
    }
    inline void predfs(int x){
        siz[x]=1,dfn[x]=++dfn[0],rev[dfn[0]]=x,L[x]=dfn[x];
        for (auto v:a[x]){
            dep[v]=dep[x]+1,predfs(v),siz[x]+=siz[v];
            if (siz[v]>siz[heavy[x]]) heavy[x]=v;
        }
        R[x]=dfn[x]+siz[x]-1;
    }
    inline int qry(int id){
        return T.query(id);
    }
    inline void del(int x){
        add(Sum,mod-qry(dfn[id1[x]])+qry(dfn[Fa[id2[x]]]));
        for (auto v:a[x]) del(v);
    }
    inline void addd(int x){
        add(Sum,qry(dfn[id1[x]])+mod-qry(dfn[Fa[id2[x]]]));
        for (auto v:a[x]) addd(v);
    }
    inline void dfs(int x){
        if (x!=1) dp[x]=Sum;
        T.update(L[x],dp[x]),T.update(R[x]+1,mod-dp[x]);
        Sum+=dp[x]*answer[x],Sum%=mod;
        // int sb=0;
        // rep(i,L[x]+1,R[x]){
        //     int id=rev[i];
        //     if (dep[id2[id]]<=dep[x] && dep[x]<=dep[id1[id]]) Sum+=dp[x],Sum%=mod,++sb;
        // }
        // answer[x]=0;
        // rep(i,L[x]+1,R[x]){
        //     int id=rev[i];
        //     if (dep[x]<=dep[id1[id]]) ++answer[x];
        //     if (dep[x]<dep[id2[id]]) --answer[x];
        // }
        // cerr<<sb<<' '<<answer[x]<<" ???\n";
        // int kel=0;
        // rep(i,1,n){
        //     if (dep[id2[x]]<=dep[i] && dep[i]<=dep[id1[x]] && L[i]<=dfn[x] && dfn[x]<=R[i])
        //         kel+=dp[i],kel%=mod;
        // }
        // cerr<<x<<" -> "<<-kel<<' '<<-qry(dfn[id1[x]])+qry(dfn[Fa[id2[x]]])<<" ???\n";
        add(Sum,mod-qry(dfn[id1[x]])+qry(dfn[Fa[id2[x]]]));
        if (heavy[x]){
            for (auto v:a[x])
                if (v^heavy[x]) del(v);
            dfs(heavy[x]);
            for (auto v:a[x])
                if (v^heavy[x]) addd(v),dfs(v);
        }
    }
    inline void work(){
        memset(T.c,0,sizeof(T.c)),
        memset(T2.c,0,sizeof(T2.c)),
        memset(T3.c,0,sizeof(T3.c));
        memset(answer,0,sizeof(answer));
        Sum=dfn[0]=0;
        memset(dp,0,sizeof(dp)),memset(heavy,0,sizeof(heavy));
        rep(i,1,n) fa[0][i]=Fa[i];
        rep(j,1,19) rep(i,1,n) fa[j][i]=fa[j-1][fa[j-1][i]];
        rep(i,1,n) id1[i]=kth(i,l[i]),id2[i]=kth(i,r[i]);
        dp[1]=1,predfs(1);
        rep(i,1,n) qrys[R[i]].push_back({i,dep[i]}),qrys[L[i]].push_back({-i,dep[i]});
        rep(i,1,n){
            int id=rev[i];
            T2.update(dep[id1[id]]+1,1),T3.update(dep[id2[id]]+1,1);
            for (auto it:qrys[i]){
                int id=it.first,T=it.second;
                if (id>0){
                    answer[id]+=T2.query(N-1)-T2.query(T);
                    answer[id]-=T3.query(N-1)-T3.query(T+1);
                }else{
                    id=-id;
                    answer[id]-=T2.query(N-1)-T2.query(T);
                    answer[id]+=T3.query(N-1)-T3.query(T+1);
                }
            }
        }
        dfn[0]=0,dfs(1);
        rep(i,2,n) cout<<dp[i]<<' ';
        cout<<'\n';
    }
}
inline void solve(){
    cin>>n,l[1]=r[1]=1,h[1]=-1e9;
    rep(i,1,n) a[i].clear();
    rep(i,2,n){
        int p;cin>>p>>l[i]>>r[i]>>h[i];
        a[p].push_back(i),Fa[i]=p;
    }
    // if (n<=5000) return BF::work();
    int tag1=1,tag2=1;
    rep(i,2,n) tag1&=l[i]==r[i],tag2&=h[i]==0;
    if (tag2) return Sub1::work();
}
signed main(){
    // freopen("ex_4.in","r",stdin);
    // freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int c,t=1;
    cin>>c>>t;
    while (t--) solve();
    // cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
    return 0;
}
源文件, 语言: C++14

詳細信息


Pretests

Pretest #1:

score: 0
Wrong Answer
time: 0ms
memory: 12928kb

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:

result:

wrong answer Answer contains longer sequence [length = 20], but output contains 0 elements

Pretest #2:

score: 0
Wrong Answer
time: 2ms
memory: 12652kb

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:

result:

wrong answer Answer contains longer sequence [length = 1196], but output contains 0 elements

Pretest #3:

score: 0
Wrong Answer
time: 0ms
memory: 13940kb

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:

result:

wrong answer Answer contains longer sequence [length = 1196], but output contains 0 elements

Pretest #4:

score: 0
Wrong Answer
time: 5ms
memory: 14212kb

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:

result:

wrong answer Answer contains longer sequence [length = 19996], but output contains 0 elements

Pretest #5:

score: 0
Wrong Answer
time: 0ms
memory: 11864kb

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:

result:

wrong answer Answer contains longer sequence [length = 19996], but output contains 0 elements

Pretest #6:

score: 0
Wrong Answer
time: 333ms
memory: 68620kb

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:

wrong answer 100000th numbers differ - expected: '6', found: '12'

Pretest #7:

score: 0
Wrong Answer
time: 415ms
memory: 67672kb

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:

wrong answer 100000th numbers differ - expected: '1', found: '301627405'

Pretest #8:

score: 0
Wrong Answer
time: 62ms
memory: 16196kb

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:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #9:

score: 0
Wrong Answer
time: 77ms
memory: 16512kb

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:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #10:

score: 0
Wrong Answer
time: 339ms
memory: 69420kb

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:

27 1160 73079 5773240 508043960 401903691 408194108 913457210 404309453 850776989 162033550 491800762 693950334 88591672 90581013 261837127 124549390 607776285 954584563 426982262 910735533 125508942 301425049 369545791 349157696 256736908 276834134 449249498 408190411 362993320 980271019 745442146 ...

result:

wrong answer 100000th numbers differ - expected: '18', found: '36'

Pretest #11:

score: 0
Wrong Answer
time: 410ms
memory: 66764kb

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:

41 1 42 3 3401 407995 8 65275757 3484 12 30977333 131377791 3443 65687153 608294415 197064986 558803128 3442 391883539 973952531 292262895 548293486 864139803 925368887 65687235 614731260 251165603 65687194 646118904 822181649 995485114 956758427 65275757 656989819 750355997 665993179 321752162 1997...

result:

wrong answer 100000th numbers differ - expected: '2', found: '766602060'

Pretest #12:

score: 0
Wrong Answer
time: 407ms
memory: 67760kb

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:

1 44 3430 45 363401 10424 49055705 17373 31271 763087444 528293936 364247389 57980118 763087444 558370737 701077016 687461217 3475 530193136 875194506 45 47291471 587072521 233025799 902397684 501363487 984008256 763090918 763087444 553932106 460519388 415423761 485110453 526953701 435687917 4594610...

result:

wrong answer 100000th numbers differ - expected: '1', found: '862489431'

Pretest #13:

score: 0
Wrong Answer
time: 64ms
memory: 16264kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #14:

score: 0
Wrong Answer
time: 69ms
memory: 16444kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #15:

score: 0
Wrong Answer
time: 77ms
memory: 16528kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #16:

score: 0
Wrong Answer
time: 78ms
memory: 16496kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #17:

score: 0
Wrong Answer
time: 73ms
memory: 18540kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #18:

score: 0
Wrong Answer
time: 77ms
memory: 16596kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #19:

score: 0
Wrong Answer
time: 77ms
memory: 16432kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Pretest #20:

score: 0
Wrong Answer
time: 75ms
memory: 16568kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Final Tests

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 12160kb

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:

result:

wrong answer Answer contains longer sequence [length = 20], but output contains 0 elements

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 12600kb

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:

result:

wrong answer Answer contains longer sequence [length = 1196], but output contains 0 elements

Test #3:

score: 0
Wrong Answer
time: 2ms
memory: 13860kb

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:

result:

wrong answer Answer contains longer sequence [length = 1196], but output contains 0 elements

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 12748kb

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:

result:

wrong answer Answer contains longer sequence [length = 19996], but output contains 0 elements

Test #5:

score: 0
Wrong Answer
time: 5ms
memory: 12980kb

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:

result:

wrong answer Answer contains longer sequence [length = 19996], but output contains 0 elements

Test #6:

score: 0
Wrong Answer
time: 318ms
memory: 68192kb

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:

wrong answer 100000th numbers differ - expected: '15', found: '30'

Test #7:

score: 0
Wrong Answer
time: 396ms
memory: 66812kb

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:

wrong answer 100000th numbers differ - expected: '1', found: '696263943'

Test #8:

score: 0
Wrong Answer
time: 71ms
memory: 16192kb

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:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #9:

score: 0
Wrong Answer
time: 76ms
memory: 16632kb

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:

result:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #10:

score: 0
Wrong Answer
time: 320ms
memory: 70188kb

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:

16 527 25807 1883910 167667973 634982620 705207129 488881034 887725160 151025554 347960978 855383206 80305903 380559379 538908054 777587576 260990688 523673420 353610155 624705377 700258326 228676702 200177699 984634103 68249951 263072670 517709689 650106087 34684922 592160972 944601706 376074738 79...

result:

wrong answer 100000th numbers differ - expected: '28', found: '56'

Test #11:

score: 0
Wrong Answer
time: 422ms
memory: 67660kb

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:

37 2478 2515 242769 38 245284 32040440 39124800 942462595 336524633 32285687 63297973 516597219 32285725 15628766 418384838 352153362 613054463 541763722 33194948 718423411 374189456 71408009 227001638 334965261 356495372 886316800 521955760 368374612 227507583 587492770 498900953 709154717 10323060...

result:

wrong answer 100000th numbers differ - expected: '2', found: '645252772'

Test #12:

score: 0
Wrong Answer
time: 430ms
memory: 67640kb

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:

69 7796 1278127 262008169 69 7796 39327 94385 55058 777304836 141577 7866 482180153 1285993 1278127 465685418 825856966 42346779 575383498 990228081 154169563 7866 833831197 726620149 749228357 498747852 817824963 482180153 41068652 699428075 474778269 447467594 402643074 564999930 7866 869370470 84...

result:

wrong answer 100000th numbers differ - expected: '45', found: '91'

Test #13:

score: 0
Wrong Answer
time: 67ms
memory: 16220kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #14:

score: 0
Wrong Answer
time: 78ms
memory: 16604kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #15:

score: 0
Wrong Answer
time: 73ms
memory: 16492kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #16:

score: 0
Wrong Answer
time: 66ms
memory: 16564kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #17:

score: 0
Wrong Answer
time: 77ms
memory: 16560kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #18:

score: 0
Wrong Answer
time: 77ms
memory: 16400kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #19:

score: 0
Wrong Answer
time: 74ms
memory: 18576kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements

Test #20:

score: 0
Wrong Answer
time: 74ms
memory: 18440kb

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:

wrong answer Answer contains longer sequence [length = 399996], but output contains 0 elements
English 繁體中文 简体中文

伺服器時間: 2024-12-05 09:48:04 | 開源專案