QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#82103#5402. 术树数zhouhuanyi50 957ms14000kbC++232.3kb2023-02-27 08:27:462023-02-27 08:27:47

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-27 08:27:47]
  • 评测
  • 测评结果:50
  • 用时:957ms
  • 内存:14000kb
  • [2023-02-27 08:27:46]
  • 提交

answer

#include<iostream>
#include<cstdio>
#define N 200000
#define M 26
using namespace std;
int read()
{
    char c=0;
    int sum=0;
    while (c<'0'||c>'9') c=getchar();
    while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
    return sum;
}
int gcd(int x,int y)
{
    if (!y) return x;
    return gcd(y,x%y);
}
int length,q,k,m,x,v;
long long sx,sy;
struct reads
{
    int d[M+1];
};
reads tmp,dp[N+1],c[M+1];
reads operator + (reads a,reads b)
{
    for (int i=0;i<=m-1;++i) a.d[i]=(a.d[i]+b.d[i])%k;
    return a;
}
reads operator * (reads a,int b)
{
    for (int i=0;i<=m-1;++i) a.d[i]=1ll*a.d[i]*b%k;
    return a;
}
reads F(int x)
{
    for (int i=0;i<=m-1;++i) tmp.d[i]=x%k,x/=k;
    return tmp;
}
int G(reads x)
{
    int res=0;
    for (int i=m-1;i>=0;--i) res=res*k+x.d[i];
    return res;
}
void exgcd(int x,int y)
{
    if (!y)
    {
	sx=1,sy=0;
	return;
    }
    exgcd(y,x%y);
    long long tx=sx;
    sx=sy,sy=tx-(x/y)*sy;
    return;
}
reads solve(int num,reads x)
{
    exgcd(x.d[num],k),sx=(sx%k+k)%k;
    return x*sx;
}
reads get_gcd(int num,reads a,reads b,reads &c)
{
    a=solve(num,a),b=solve(num,b),exgcd(a.d[num],b.d[num]),sx=(sx%k+k)%k,sy=(sy%k+k)%k;
    if (sx) c=b;
    else c=a;
    return a*sx+b*sy;
}
void Insert(reads x)
{
    int ds;
    reads y;
    for (int i=m-1;i>=0;--i)
	if (x.d[i])
	{
	    if (!c[i].d[i]) c[i]=x,ds=k/gcd(x.d[i],k),x=x*ds;
	    else c[i]=get_gcd(i,c[i],x,y),ds=(k-y.d[i])/c[i].d[i],x=y+c[i]*ds;
	}
    return;
}
reads query(reads x)
{
    int ds,dst;
    reads y;
    for (int i=m-1;i>=0;--i)
	if (x.d[i]&&c[i].d[i])
	    y=solve(i,c[i]),ds=x.d[i]%y.d[i],dst=((ds-x.d[i])/y.d[i]+k)%k,x=x+y*dst;
    return x;
}
int main()
{
    int op,x,y,v;
    q=read(),k=read(),m=read();
    if (k&1)
    {
	while (q--)
	{
	    op=read();
	    if (op==1) x=read(),v=read();
	    else if (op==2) x=read(),y=read(),v=read();
	    else x=read(),y=read(),puts("0");
	}
	return 0;
    }
    length=1;
    while (q--)
    {
	op=read();
	if (op==1) x=read(),v=read(),dp[++length]=dp[x]+F(v),Insert(F(v)+F(v));
	else if (op==2) x=read(),y=read(),v=read(),Insert(dp[x]+dp[y]+F(v));
	else x=read(),y=read(),printf("%d\n",G(query(dp[x]+dp[y])));
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 2ms
memory: 3216kb

input:

30 7 3
1 1 301
1 1 236
1 2 278
3 2 4
3 2 4
2 1 4 265
1 1 242
1 4 278
1 6 337
3 2 3
2 5 7 304
2 5 6 34
1 4 178
3 6 7
3 5 7
3 1 4
1 1 178
3 3 4
3 1 6
3 3 4
2 6 7 131
1 1 213
3 1 3
2 3 10 11
3 4 6
2 5 9 169
1 6 9
2 5 10 29
1 9 111
3 9 11

output:

0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 12 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3252kb

input:

30 9 3
1 1 694
1 2 251
1 2 623
2 2 4 109
3 3 4
3 1 2
2 2 4 611
1 4 595
2 2 5 477
2 2 5 363
3 1 3
2 1 5 121
1 2 225
2 1 5 214
2 3 6 706
3 3 4
2 2 3 122
2 2 3 621
3 2 3
3 2 4
2 1 5 630
1 5 598
3 4 5
3 1 3
1 2 665
2 1 2 331
2 1 6 449
1 2 387
3 3 6
3 4 6

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

30 4 5
1 1 854
1 1 467
1 2 708
2 2 4 529
1 4 115
1 4 444
2 3 4 108
2 2 5 724
2 1 3 375
1 5 827
2 5 6 974
1 3 73
3 2 3
2 2 3 140
3 5 6
2 6 8 787
3 1 5
1 5 971
3 4 6
2 4 5 816
3 7 8
3 2 4
1 6 855
2 5 10 39
2 6 9 280
2 6 10 662
3 7 10
1 6 412
3 4 7
1 6 276

output:

0
256
256
256
0
0
0
0

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

30 6 4
1 1 1246
1 1 825
1 3 843
2 1 3 186
2 2 3 228
2 1 3 1187
3 2 3
3 1 4
1 3 942
3 1 2
1 5 779
2 3 4 775
2 1 2 275
2 1 3 309
2 5 6 1175
3 2 6
1 6 1084
3 4 6
1 7 176
3 5 6
2 3 8 431
3 2 6
3 1 4
1 8 725
3 7 9
3 1 4
3 6 7
3 2 4
3 1 6
1 5 972

output:

1
6
7
0
0
0
0
0
0
0
0
0
0

result:

ok 13 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

30 6 4
1 1 1050
1 2 312
1 3 665
2 1 4 49
2 1 3 394
2 3 4 1225
3 1 4
1 1 381
3 1 2
1 3 933
1 3 551
2 2 6 521
3 3 5
2 2 6 1219
3 3 7
1 6 953
1 3 403
2 1 7 624
1 8 981
3 1 2
1 9 1052
2 4 9 971
2 5 8 575
3 1 7
2 6 9 953
2 1 10 347
3 3 11
2 3 9 878
1 6 991
2 6 11 681

output:

1
0
1
1
0
0
0

result:

ok 7 lines

Test #6:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

30 4 5
1 1 48
1 2 924
1 2 587
3 3 4
2 1 3 63
1 1 600
2 2 5 747
1 5 252
2 2 5 777
2 2 3 119
1 3 914
1 1 708
2 2 3 670
2 3 5 526
3 3 7
1 5 816
1 9 401
1 2 364
2 7 10 16
2 10 11 254
1 6 641
1 10 406
2 6 10 324
1 5 29
1 12 493
2 3 15 125
1 12 95
1 4 370
2 8 16 766
1 11 307

output:

341
0

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 3256kb

input:

30 3 6
1 1 358
1 2 16
1 1 636
1 1 156
1 4 512
3 3 4
3 5 6
3 1 2
2 2 5 271
3 4 6
2 3 5 5
1 2 566
3 3 4
3 4 6
3 2 3
2 4 6 472
2 2 6 119
1 1 260
2 1 8 488
1 7 345
1 8 368
2 6 9 649
1 1 553
2 1 9 416
3 8 9
1 10 630
1 9 156
1 3 14
1 4 407
3 4 10

output:

0
0
0
0
0
0
0
0
0

result:

ok 9 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

3 8 3
1 1 401
1 2 0
3 1 2

output:

179

result:

ok single line: '179'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #9:

score: 11
Accepted
time: 3ms
memory: 3420kb

input:

996 4 8
1 1 43515
1 1 674
1 1 0
3 3 4
1 3 26873
3 3 5
3 3 4
1 2 0
1 5 26201
1 7 0
3 1 3
3 2 6
1 2 2722
1 4 674
1 10 35328
3 3 5
1 2 2048
3 10 11
2 2 8 34808
3 10 11
3 1 4
3 3 11
3 3 7
3 1 2
1 2 10753
3 12 13
3 3 4
1 12 32928
3 9 13
3 3 8
2 3 10 3
3 5 8
1 9 34978
1 13 2722
3 8 14
3 2 3
1 9 43681
3 7 ...

output:

0
26873
0
0
0
24825
0
0
0
0
1024
504
0
0
0
1024
17496
1528
504
1528
16640
504
1024
1528
1528
16640
16472
16640
16472
0
0
504
504
504
0
16640
1024
504
504
504
0
0
504
0
504
16640
0
504
0
504
16640
16640
16640
0
0
0
0
0
504
0
0
16472
0
0
1024
1024
504
504
0
504
0
16640
504
0
0
0
504
16640
0
0
504
504
...

result:

ok 459 lines

Test #10:

score: 0
Accepted
time: 3ms
memory: 3528kb

input:

997 6 6
1 1 12369
1 1 31248
3 1 2
2 1 2 43616
3 1 2
3 1 2
1 1 15625
1 4 15627
3 2 4
1 1 31251
1 1 31249
3 3 6
1 5 31253
1 3 4
1 7 31252
1 2 3
1 7 15626
3 6 7
1 4 15627
3 5 12
1 6 2
1 12 0
3 4 6
3 8 14
3 1 7
1 8 31252
1 6 4
3 12 17
1 9 31249
1 10 0
1 18 4
3 5 19
1 8 12861
1 3 16431
1 5 16155
1 16 405...

output:

12369
12366
12366
12366
0
0
0
0
0
0
0
0
0
9474
9474
9474
0
0
0
0
0
9330
9330
9330
0
9330
9330
9330
0
0
0
0
0
9330
9330
0
9330
0
0
0
0
9330
0
9330
9330
0
0
0
0
9330
9330
9330
9330
9330
9330
0
0
9330
0
0
9330
0
0
9330
9330
0
9330
9330
9330
9330
0
0
0
9330
0
0
0
9330
9330
9330
9330
0
9330
9330
9330
933...

result:

ok 454 lines

Test #11:

score: 0
Accepted
time: 3ms
memory: 3672kb

input:

1000 8 5
1 1 14822
3 1 2
2 1 2 20801
3 1 2
3 1 2
3 1 2
3 1 2
1 2 8322
1 2 2337
1 4 10659
3 3 4
3 1 2
3 1 3
1 4 18469
1 4 18469
3 5 7
3 3 4
1 6 7608
3 1 6
3 3 5
1 3 2226
1 5 26902
2 3 6 289
1 3 26672
1 1 10547
1 2 16530
3 10 13
1 3 10263
3 7 9
1 8 10257
1 8 26674
1 10 16531
1 16 26899
3 2 13
3 1 9
1 ...

output:

6498
4161
4161
4161
4161
0
4161
4161
0
0
4161
0
0
0
0
4160
4160
4160
5160
1112
5160
5160
0
4160
0
0
0
0
0
0
0
5160
5160
0
0
1112
5160
0
0
5160
0
0
0
0
0
0
5160
5160
0
5160
0
0
0
0
0
1112
0
5160
5160
0
0
0
5160
5160
5160
5160
5160
0
5160
0
0
5160
0
4104
0
0
4104
4104
4104
0
0
0
0
0
0
4104
0
4104
4104...

result:

ok 446 lines

Test #12:

score: 0
Accepted
time: 2ms
memory: 3512kb

input:

994 12 4
1 1 12377
1 2 18746
3 2 3
3 1 3
2 2 3 11
1 3 18751
3 3 4
1 1 7587
1 4 7592
1 2 18753
2 3 6 7586
2 5 7 16102
1 5 6
3 5 7
2 6 7 7591
3 4 6
2 5 6 6526
2 1 4 19821
3 3 5
3 2 8
1 1 11307
1 7 7595
3 1 6
1 9 15032
1 2 18748
2 2 10 15027
3 8 11
1 4 7591
3 4 7
3 6 11
2 2 10 15033
3 1 4
1 12 3865
1 1...

output:

0
2807
0
2796
0
2796
2796
2796
0
0
2796
2796
0
2796
2796
0
2796
0
0
2796
0
0
0
2796
2796
0
0
0
0
0
2796
0
2796
0
0
2796
0
0
0
2796
0
0
2796
2796
2796
2796
2796
0
2796
0
2796
2796
0
2796
2796
0
0
0
2796
0
0
0
0
2796
0
0
2796
0
2796
2796
2796
0
0
1932
0
1932
1932
1932
0
0
1932
1788
0
0
1932
1932
1932
...

result:

ok 459 lines

Test #13:

score: -11
Wrong Answer
time: 3ms
memory: 3676kb

input:

995 30 3
1 1 23137
1 2 384
1 1 192
3 2 4
1 2 18728
1 5 18566
3 2 4
1 2 9364
1 3 546
2 2 6 9555
3 1 3
3 3 8
3 2 8
3 3 5
2 2 8 557
3 4 7
1 2 9741
3 6 7
3 2 5
1 8 16
1 7 541
3 3 8
3 1 8
1 2 9730
1 3 18188
3 5 11
1 1 18555
3 4 5
3 1 6
3 9 13
3 2 4
1 13 389
1 11 9725
1 11 749
1 15 18014
3 11 13
1 7 9007
...

output:

4601
4601
4591
0
0
1
4591
0
0
0
4590
0
4590
4590
0
4590
0
0
0
0
4590
0
0
0
4590
0
0
0
0
4590
0
4590
4590
4590
0
0
0
0
0
0
4590
0
0
4590
0
4590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4590
0
0
0
0
0
0
0
0
4590
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

wrong answer 3rd lines differ - expected: '4590', found: '4591'

Subtask #3:

score: 11
Accepted

Test #21:

score: 11
Accepted
time: 13ms
memory: 3284kb

input:

198517 3 16
1 1 40710744
1 2 21885097
1 1 23592366
1 4 7387074
1 5 16074177
1 1 41027400
1 4 18082971
1 2 12822448
1 1 2286557
1 1 27896295
1 11 14532760
1 8 2357296
1 11 9190559
1 6 40503152
3 4 11
3 1 7
3 3 7
3 8 14
3 12 15
3 2 3
1 10 34606866
1 13 42718465
1 16 30353561
3 5 11
3 2 6
3 16 18
1 3 2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99662 lines

Test #22:

score: 0
Accepted
time: 501ms
memory: 13916kb

input:

198073 8 8
1 1 4007183
1 1 411647
1 1 3301064
1 1 2747675
1 3 11141272
1 3 4308435
1 4 15582931
1 5 11340890
1 2 9172283
1 9 542280
1 10 12209796
1 3 2829956
3 1 3
1 3 724504
3 2 14
3 3 14
3 9 12
3 7 10
1 1 3594204
1 14 13600647
1 15 4589767
3 10 14
1 4 10564184
1 13 1781174
1 19 6067505
1 9 6735060...

output:

262729
2097224
520
4673
2097672
2134081
2101769
2134080
2101832
2130432
584
2129992
2392584
2134024
2101824
2363904
295424
36864
4608
0
295489
299593
1
33353
2359305
2130440
2130497
2363969
4161
294976
37440
2359361
299080
2101248
299592
33344
2392576
2359816
2097160
8
2359880
262657
2101832
2363464...

result:

ok 99445 lines

Test #23:

score: 0
Accepted
time: 224ms
memory: 14000kb

input:

198343 50 4
1 1 4597949
1 1 1140260
1 1 1078946
1 3 4494430
1 4 3030702
1 5 5215333
1 4 5366961
1 2 4836213
1 5 3721812
1 1 486900
1 3 2631122
3 7 11
1 1 384111
3 6 10
3 1 3
1 1 6239546
3 6 10
1 5 4354709
3 11 12
3 6 13
1 9 863486
1 15 5296752
1 12 1997611
3 15 16
1 11 6087993
3 1 13
1 9 4926906
3 1...

output:

2551
125050
125050
125050
125050
125001
1
127501
127550
125050
125000
2500
2550
125000
125001
50
50
51
50
127550
127501
2500
125000
50
127500
2550
125000
50
127500
125051
1
2550
127551
51
127501
1
127551
2500
125000
2551
2551
125000
127501
1
50
51
2551
2550
125001
0
2500
125001
2500
50
127500
125001...

result:

ok 99620 lines

Test #24:

score: 0
Accepted
time: 12ms
memory: 3312kb

input:

199495 2675 2
1 1 6874452
1 1 2927709
1 1 4714827
1 1 341697
1 1 5807384
1 2 6029400
1 6 3410507
1 1 4255734
1 9 7116423
1 3 5647617
3 5 11
1 5 2479935
3 9 10
3 2 6
1 4 6921813
1 12 4608236
1 11 932260
1 11 5347104
3 1 11
3 11 14
1 12 715746
3 8 17
1 14 1418580
1 3 6123273
1 4 6481423
1 1 4166639
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100058 lines

Test #25:

score: 0
Accepted
time: 16ms
memory: 3256kb

input:

199531 45237947 1
1 1 15260546
1 1 30197693
1 2 3455446
1 1 29660068
1 5 5406610
1 2 32468080
1 6 33471078
1 7 3670881
1 7 11684247
1 7 8493599
1 1 4296342
3 5 6
1 9 41359920
3 2 11
1 4 37376116
3 2 5
1 9 44209222
3 2 14
1 13 11322652
3 11 13
1 7 3505613
1 14 30321158
1 3 3184527
1 11 14996243
1 19 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 99829 lines

Subtask #4:

score: 19
Accepted

Test #26:

score: 19
Accepted
time: 54ms
memory: 10464kb

input:

198891 26426880 1
1 1 0
2 1 2 0
3 1 2
1 1 0
3 2 3
3 1 2
1 2 0
1 2 0
1 3 0
1 6 0
2 1 6 0
2 3 6 0
3 2 3
1 2 13213440
1 2 13213440
1 4 13213440
3 4 10
1 1 13213440
2 3 4 0
2 3 8 13213440
1 1 0
1 12 0
1 13 0
1 3 0
3 2 11
3 2 12
2 11 14 13213440
1 6 0
2 12 14 0
2 1 2 0
1 10 0
1 12 0
2 3 13 0
3 12 14
3 1 ...

output:

0
0
0
0
13213440
13213440
0
0
0
13213440
0
0
13213440
0
13213440
0
13213440
0
13213440
13213440
13213440
13213440
13213440
0
13213440
13213440
0
13213440
13213440
0
0
0
13213440
0
13213440
0
13213440
0
0
0
13213440
13213440
0
13213440
13213440
13213440
13213440
0
13213440
13213440
13213440
13213440
...

result:

ok 66344 lines

Test #27:

score: 0
Accepted
time: 53ms
memory: 10352kb

input:

199011 22494024 1
1 1 11247012
1 1 11247012
2 1 2 11247012
3 1 3
1 3 11247012
2 1 4 0
1 1 11247012
1 2 11247012
2 4 5 11247012
3 1 2
1 5 0
3 2 5
2 5 6 11247012
2 2 3 0
1 1 11247012
3 4 8
2 1 5 11247012
3 5 7
1 6 11247012
1 4 0
3 1 7
2 1 9 11247012
1 7 11247012
2 3 4 11247012
3 4 5
2 1 9 11247012
3 5...

output:

11247012
11247012
0
11247012
0
11247012
11247012
11247012
0
11247012
0
0
0
11247012
11247012
11247012
11247012
11247012
11247012
11247012
0
11247012
11247012
11247012
11247012
11247012
11247012
0
0
0
11247012
11247012
11247012
0
0
0
0
11247012
0
11247012
11247012
0
11247012
0
0
11247012
0
11247012
1...

result:

ok 66431 lines

Test #28:

score: 0
Accepted
time: 71ms
memory: 10460kb

input:

198242 23269680 1
1 1 11634840
2 1 2 11634840
3 1 2
2 1 2 11634840
1 1 11634840
1 1 0
1 2 0
1 1 0
2 2 6 11634840
2 2 6 11634840
3 4 6
3 5 6
1 6 11634840
2 3 6 11634840
3 2 7
2 2 5 0
2 2 3 0
2 2 3 0
2 3 7 0
2 2 3 0
3 1 3
3 2 5
2 1 3 11634840
3 3 6
3 2 5
3 5 7
2 1 6 0
1 4 0
1 4 11634840
2 7 8 11634840...

output:

11634840
0
11634840
0
11634840
0
11634840
0
0
0
0
11634840
11634840
0
11634840
11634840
0
0
11634840
0
11634840
11634840
11634840
11634840
11634840
11634840
11634840
11634840
11634840
0
11634840
11634840
11634840
11634840
0
11634840
11634840
11634840
11634840
0
0
11634840
0
11634840
11634840
1163484...

result:

ok 66135 lines

Test #29:

score: 0
Accepted
time: 52ms
memory: 10468kb

input:

198177 22462440 1
1 1 15723708
3 1 2
1 2 0
3 2 3
2 2 3 17969952
2 1 2 20216196
1 1 15723708
3 2 3
2 1 3 11231220
2 1 2 11231220
1 1 11231220
2 1 3 2246244
2 1 2 20216196
3 3 4
1 4 8984976
2 5 6 4492488
2 3 6 4492488
2 2 5 4492488
1 4 17969952
1 6 20216196
3 3 7
1 1 15723708
1 4 0
3 3 9
3 1 5
1 7 449...

output:

2246244
0
0
0
0
0
2246244
2246244
2246244
0
0
2246244
0
0
0
0
2246244
2246244
0
2246244
0
0
0
0
0
2246244
2246244
0
0
2246244
2246244
0
0
0
2246244
2246244
2246244
0
2246244
0
2246244
0
0
0
0
2246244
0
0
2246244
2246244
0
0
0
0
2246244
0
2246244
0
0
0
2246244
0
2246244
2246244
2246244
0
2246244
0
22...

result:

ok 66146 lines

Subtask #5:

score: 15
Accepted

Test #30:

score: 15
Accepted
time: 920ms
memory: 10732kb

input:

199458 2 25
1 1 31252443
2 1 2 22827339
1 2 13517756
1 2 5635412
1 3 33397078
1 3 33542998
2 3 5 1484991
3 5 6
2 1 3 7938846
2 1 2 3665458
1 3 29150948
3 4 5
1 3 733545
1 7 4698781
1 7 21699192
1 6 10854390
3 3 8
3 4 8
1 2 6889338
2 1 12 27646676
2 6 8 24407215
1 11 20847453
3 4 13
1 6 16891344
3 4 ...

output:

150016
891079
733545
1048849
7306736
7012
6336311
7310241
705870
794721
112806
777734
2522042
203310
370916
2339461
699806
747148
597151
969956
2633367
376785
884917
884917
331441
2696956
2423527
2304668
2457533
2783258
690228
864462
360811
124716
2098167
48248
2869827
605003
235881
2739062
2861794
...

result:

ok 66461 lines

Test #31:

score: 0
Accepted
time: 917ms
memory: 10452kb

input:

198986 2 25
1 1 11331234
1 2 24833898
2 1 3 10628416
3 2 3
1 3 6115878
2 2 4 23717273
1 3 18406568
2 2 4 1949969
1 4 6063130
1 6 25760596
3 1 2
3 5 7
3 5 6
3 2 6
3 1 7
1 6 31753825
3 1 4
2 3 4 6115878
3 2 6
2 3 5 22447229
3 1 3
2 3 4 6115878
2 4 7 1813362
3 2 4
2 1 8 8192320
3 3 5
1 7 114729
1 9 188...

output:

969698
11331234
9443776
2324169
990686
1086581
11610035
990686
10628416
1949969
2269429
1949969
571284
3254790
682010
502346
824812
623366
377762
377762
2376509
884877
2316090
2244147
665245
341785
922389
928237
744294
69811
404242
789948
620664
513259
317968
222762
169970
969698
12365
1046658
91964...

result:

ok 65927 lines

Test #32:

score: 0
Accepted
time: 957ms
memory: 10452kb

input:

198119 2 25
1 1 1988220
2 1 2 10935842
2 1 2 10935842
3 1 2
1 2 9175257
2 1 2 30426983
1 3 21520990
1 2 7244347
2 3 5 19700729
1 3 24753647
3 4 6
2 1 2 30426983
3 2 4
1 6 25686082
2 1 6 22244116
1 7 20608501
3 3 6
1 2 29561714
2 2 3 21107138
1 1 21122181
1 6 7460982
2 7 9 19503627
1 9 8058976
3 1 8
...

output:

1988220
3266481
684956
994474
48107
1167209
4443137
4685362
1360512
4639448
238700
348592
278885
295451
489693
344667
180320
328346
407326
454344
485048
139415
148539
301162
209675
136220
454344
201497
48475
346271
411773
397728
487925
400145
418154
120548
273314
523155
476405
141994
243836
128983
7...

result:

ok 65949 lines

Subtask #6:

score: 3
Accepted

Test #33:

score: 3
Accepted
time: 6ms
memory: 3220kb

input:

49958 1023 2
1 1 122428
1 1 917186
2 2 3 53148
1 3 876461
2 1 3 968146
2 2 4 569341
2 3 4 199413
2 1 4 238371
1 3 127427
1 2 887225
2 1 4 776059
2 4 6 155479
2 1 6 795533
1 5 159578
3 5 6
2 2 5 758778
2 5 6 601115
3 4 7
1 4 202224
2 5 6 902346
3 1 6
3 5 7
3 3 5
1 2 791251
1 5 502214
2 6 7 929048
1 6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 16607 lines

Test #34:

score: 0
Accepted
time: 27ms
memory: 3252kb

input:

198392 7 9
1 1 23598910
3 1 2
1 1 25616681
2 1 2 22101090
2 2 3 25455751
3 1 2
3 1 2
1 3 25668120
3 1 3
1 3 23878180
1 4 10885281
1 1 5873751
2 2 7 31608236
3 2 3
3 3 5
2 2 6 37313936
2 1 6 36853293
2 4 7 6773989
2 1 7 19143946
3 2 7
3 3 7
3 1 2
1 1 31756932
3 3 6
2 5 8 39585364
1 2 27162269
3 4 5
2...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 65758 lines

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%