QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#668559	#9491. 生命的循环	zjy0001	100 ✓	623ms	217592kb	C++17	3.1kb	2024-10-23 14:58:57	2024-10-23 14:59:03

Judging History

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

[2024-10-23 14:59:03]
评测

测评结果：100
用时：623ms
内存：217592kb

查看

[2024-10-23 14:58:57]
提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=5e3+5,M=105,K=1.1e6+5,Mod=1e9+9;
int n,m,B,V,typ,ans,pn;
bitset<K>h[M];
int kmp[K],f[2][N][N],g[M][M];
vector<pair<int,int>>G[N],R[N];
int vs[M],vp[M],pr[M],bl[M],blk[M],pe[M];
int tim,scc,stop,dfn[N],low[N],col[N],st[N],d[N],E[N];
inline void tarjan(int u){
	dfn[u]=low[u]=++tim,st[++stop]=u;
	for(auto [v,w]:G[u])
		if(!dfn[v])d[v]=d[u]+w,tarjan(v),low[u]=min(low[u],low[v]);
		else if(!col[v])low[u]=min(low[u],dfn[v]);
	if(low[u]>=dfn[u]){
		++scc;
		for(int i=-1;i!=u;)
			i=st[stop--],col[i]=scc;
	}
}
inline void bfs(int t,vector<pair<int,int>>*Gr,int s,int k){
	queue<pair<int,int>>Q;
	Q.emplace(s,0),f[t][s][0]=1;
	while(!Q.empty()){
		auto [u,d]=Q.front();Q.pop();
		for(auto [v,w]:Gr[u])if(!f[t][v][(d+w)%k])
			f[t][v][(d+w)%k]=1,Q.emplace(v,(d+w)%k);
	}
}
inline void sieve(int n){
	for(int i=2;i<=n;++i){
		if(!vp[i])pr[++pn]=i;
		for(int j=1,k;j<=pn&&(k=i*pr[j])<=n;++j){
			vp[k]=1;
			if(i%pr[j]==0)break;
		}
	}
	pr[pn+1]=n+1,vs[1]=1,bl[1]=1,V=1;
	for(int i=1;i<=pn;++i){
		int c=1,d=1;
		while(c*pr[i]*pr[i+1]<=n)c*=pr[i];
		while(d*pr[i]<=n)d*=pr[i];
		int q=d/c;
		d=1;
		while(d<=c)blk[d]=1,d*=pr[i];
		while(d<=n)blk[d]=q,d*=pr[i];
		vs[q]=1,V*=c;
	}
	for(int i=1;i<=n;++i){
		int c=i,d=V,r=1;
		for(int j=1;j<=pn;++j)if(c%pr[j]==0){
			int k=0;
			while(c%pr[j]==0)++k,c/=pr[j];
			for(int l=1;l<k;++l)if(d%pr[j]==0)d/=pr[j];
			if(d%pr[j])while(k--)r*=pr[j];
		}
		bl[i]=blk[r];
	}
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>typ;
	for(int i=1;i<=m;++i){
		int u,v,w;cin>>u>>v>>w;
		G[u].emplace_back(v,w);
		R[v].emplace_back(u,w);
	}
	tarjan(1);
	if(!dfn[n])return cout<<"1\n",0;
	for(int u=1;u<=n;++u)if(col[u])
		for(auto [v,w]:G[u])if(col[u]==col[v])
			E[col[u]]=abs(__gcd(E[col[u]],w+d[u]-d[v]));
	B=*max_element(E+1,E+scc+1);
	if(!B)return cout<<"1\n",0;
	sieve(B);
	for(int k=1;k<=B;++k){
		for(int i=1;i<=n;++i)
			fill_n(f[0][i],k,0),fill_n(f[1][i],k,0);
		bfs(0,G,1,k),bfs(1,R,n,k);
		for(int i=1;i<=n;++i)if(E[col[i]]==k)
			for(int x=0;x<k;++x)for(int y=0;y<k;++y)
				if(f[0][i][x]&&f[1][i][y])g[k][(x+y)%k]=1;
		int r=bl[k];
		for(int x=0,t=0;x<r*V/k;++x)
			for(int y=0;y<k;++y,++t)
				if(g[k][y])h[r][t]=1;
	}
	for(int i=0;i<V;++i){
		bool flg=0;
		for(int k=1;k<=B;++k)if(vs[k]){
			bool ok=1;
			for(int j=0,t=i;j<k;++j,t+=V)if(!h[k][t]){ok=0;break;}
			if(ok){flg=1;break;}
		}
		if(flg)for(int k=1;k<=B;++k)if(vs[k])
			for(int j=0,t=i;j<k;++j,t+=V)h[k][t]=1;
	}
	for(int k=1;k<=B;++k)if(vs[k]){
		int r=k*V;
		h[k][r]=h[k][0];
		for(int i=2,j=0;i<=r;++i){
			for(;j&&h[k][j+1]!=h[k][i];j=kmp[j]);
			kmp[i]=(j+=(h[k][j+1]==h[k][i]));
		}
		int l=kmp[r];
		for(;l&&r%(r-l);l=kmp[l]);
		l=r-l;
		for(int i=2;i<=B;++i)if(l%i==0){
			int c=0;
			while(l%i==0)l/=i,++c;
			pe[i]=max(pe[i],c);
		}
	}
	ans=1;
	for(int i=1;i<=B;++i)while(pe[i]--)ans=1ll*ans*i%Mod;
	cout<<ans;
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 1ms

memory: 5668kb

input:

output:

result:

ok single line: '1'

Test #2:

score: 1

Accepted

time: 2ms

memory: 4152kb

input:

3000 10000 1
2941 1762 34
1456 1466 41
1279 2756 45
396 2841 46
579 12 78
2654 888 18
1656 237 58
1820 2775 80
426 165 3
994 1141 92
1617 1851 28
2449 2082 75
1438 2206 34
2657 774 78
942 1156 40
2329 176 92
858 2172 84
1161 2798 72
982 435 43
1674 1274 88
2827 979 9
1003 1165 50
907 774 81
1142 204...

output:

result:

ok single line: '1'

Subtask #2:

score: 8

Accepted

Test #3:

score: 8

Accepted

time: 1ms

memory: 9908kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 8

Accepted

time: 1ms

memory: 9988kb

input:

output:

result:

ok single line: '60'

Test #5:

score: 8

Accepted

time: 1ms

memory: 12016kb

input:

output:

result:

ok single line: '120'

Subtask #3:

score: 11

Accepted

Test #6:

score: 11

Accepted

time: 11ms

memory: 203092kb

input:

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

output:

result:

ok single line: '14'

Test #7:

score: 11

Accepted

time: 24ms

memory: 88288kb

input:

2000 2189 3
1 2 0
2 1 0
2 3 0
3 4 0
4 2 0
2 5 0
5 2 0
3 6 25
6 3 23
2 18 4
18 16 0
16 8 5
8 9 3
9 19 8
19 12 5
12 23 1
23 24 6
24 10 5
10 15 6
15 17 6
17 21 9
21 22 4
22 7 6
7 25 5
25 11 4
11 20 5
20 13 5
13 14 6
14 2 3
17 26 0
26 17 0
26 28 0
28 27 0
27 26 0
3 93 0
93 70 1
70 158 0
158 95 1
95 189 ...

output:

result:

ok single line: '48'

Test #8:

score: 11

Accepted

time: 0ms

memory: 14140kb

input:

output:

result:

ok single line: '3'

Subtask #4:

score: 10

Accepted

Dependency #3:

100%

Accepted

Test #9:

score: 10

Accepted

time: 26ms

memory: 203304kb

input:

5000 5287 4
1 2 41
1 20 1
20 21 2
21 38 1
38 32 1
32 40 0
40 8 3
8 35 2
35 15 0
15 19 2
19 31 2
31 12 1
12 50 4
50 36 3
36 5 1
5 22 1
22 43 2
43 26 0
26 25 3
25 23 0
23 17 3
17 42 1
42 13 4
13 9 3
9 37 1
37 52 2
52 4 1
4 49 1
49 48 3
48 24 1
24 6 0
6 55 2
55 30 0
30 18 0
18 11 1
11 14 0
14 51 2
51 1...

output:

result:

ok single line: '30'

Test #10:

score: 10

Accepted

time: 295ms

memory: 203768kb

input:

5000 10000 4
4998 4999 12
4999 5000 18
5000 4998 42
1 2 17
2 3 43
3 4 12
4 5 32
5 6 10
6 7 45
7 8 22
8 9 17
9 10 45
10 11 33
11 12 1
12 13 10
13 14 2
14 15 43
15 16 27
16 17 23
17 18 23
18 19 30
19 20 9
20 21 19
21 22 30
22 23 20
23 24 8
24 25 29
25 26 18
26 27 34
27 28 4
28 29 47
29 30 36
30 31 32
...

output:

result:

ok single line: '12'

Subtask #5:

score: 19

Accepted

Test #11:

score: 19

Accepted

time: 417ms

memory: 53904kb

input:

767 10000 5
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 2 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 13 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
...

output:

result:

ok single line: '1'

Test #12:

score: 19

Accepted

time: 72ms

memory: 26508kb

input:

output:

381798563

result:

ok single line: '381798563'

Test #13:

score: 19

Accepted

time: 73ms

memory: 24520kb

input:

output:

672589923

result:

ok single line: '672589923'

Test #14:

score: 19

Accepted

time: 41ms

memory: 22512kb

input:

output:

result:

ok single line: '1'

Test #15:

score: 19

Accepted

time: 35ms

memory: 22364kb

input:

output:

868803081

result:

ok single line: '868803081'

Subtask #6:

score: 9

Accepted

Test #16:

score: 9

Accepted

time: 39ms

memory: 28148kb

input:

output:

result:

ok single line: '7398268'

Test #17:

score: 9

Accepted

time: 3ms

memory: 20448kb

input:

output:

result:

ok single line: '16'

Test #18:

score: 9

Accepted

time: 30ms

memory: 22524kb

input:

output:

714737421

result:

ok single line: '714737421'

Test #19:

score: 9

Accepted

time: 397ms

memory: 54052kb

input:

767 10000 6
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 2 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 13 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
39 40 1
...

output:

result:

ok single line: '1'

Test #20:

score: 9

Accepted

time: 16ms

memory: 203376kb

input:

5000 10000 6
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '9'

Subtask #7:

score: 18

Accepted

Test #21:

score: 18

Accepted

time: 0ms

memory: 18188kb

input:

output:

result:

ok single line: '1'

Test #22:

score: 18

Accepted

time: 0ms

memory: 14176kb

input:

output:

result:

ok single line: '3063060'

Test #23:

score: 18

Accepted

time: 0ms

memory: 12056kb

input:

output:

result:

ok single line: '3423420'

Test #24:

score: 18

Accepted

time: 1ms

memory: 12256kb

input:

output:

346393023

result:

ok single line: '346393023'

Test #25:

score: 18

Accepted

time: 2ms

memory: 16076kb

input:

output:

528923553

result:

ok single line: '528923553'

Test #26:

score: 18

Accepted

time: 0ms

memory: 12044kb

input:

output:

result:

ok single line: '1492260'

Test #27:

score: 18

Accepted

time: 3ms

memory: 201272kb

input:

5000 10000 7
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '3'

Test #28:

score: 18

Accepted

time: 0ms

memory: 18172kb

input:

output:

89541839

result:

ok single line: '89541839'

Test #29:

score: 18

Accepted

time: 0ms

memory: 14168kb

input:

output:

160733989

result:

ok single line: '160733989'

Test #30:

score: 18

Accepted

time: 2ms

memory: 14128kb

input:

output:

767157300

result:

ok single line: '767157300'

Test #31:

score: 18

Accepted

time: 0ms

memory: 14128kb

input:

output:

362040671

result:

ok single line: '362040671'

Test #32:

score: 18

Accepted

time: 2ms

memory: 14184kb

input:

output:

result:

ok single line: '414120'

Test #33:

score: 18

Accepted

time: 12ms

memory: 71720kb

input:

1452 2220 7
1 525 0
525 925 1
925 1043 1
1043 825 0
825 831 0
831 804 1
804 121 1
121 1012 1
1012 1114 1
1114 1398 0
1398 264 1
264 235 0
235 1284 0
1284 1020 0
1020 792 0
792 375 1
375 885 1
885 1411 1
1411 1027 1
1027 857 0
857 180 1
180 1361 1
1361 565 1
565 1430 0
1430 404 1
404 1156 0
1156 646 ...

output:

result:

ok single line: '7020'

Test #34:

score: 18

Accepted

time: 8ms

memory: 69848kb

input:

1452 2239 7
1 1117 1
1117 693 0
693 1182 1
1182 1200 1
1200 105 1
105 138 0
138 893 0
893 1136 0
1136 622 0
622 843 0
843 954 0
954 820 0
820 1139 1
1139 1362 0
1362 509 1
509 525 1
525 1381 1
1381 7 1
7 499 0
499 534 1
534 407 0
407 29 1
29 1436 1
1436 197 0
197 930 0
930 1410 0
1410 337 1
337 971 ...

output:

result:

ok single line: '9828'

Test #35:

score: 18

Accepted

time: 80ms

memory: 203348kb

input:

4932 9860 7
1 872 1
872 900 0
900 1617 1
1617 3242 1
3242 380 0
380 178 1
178 3702 0
3702 4866 1
4866 4846 1
4846 1086 0
1086 41 1
41 1271 1
1271 4767 1
4767 3082 1
3082 3759 1
3759 2723 1
2723 1808 0
1808 2024 1
2024 971 0
971 3935 0
3935 665 0
665 2597 0
2597 3670 0
3670 387 0
387 1573 1
1573 2869...

output:

89541839

result:

ok single line: '89541839'

Subtask #8:

score: 24

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Dependency #7:

100%

Accepted

Test #36:

score: 24

Accepted

time: 608ms

memory: 180588kb

input:

3962 9999 8
1 1680 1
1680 3471 0
3471 720 1
720 2007 0
2007 3915 1
3915 133 0
133 3169 0
3169 2083 0
2083 3651 1
3651 2976 1
2976 1165 1
1165 3516 1
3516 3789 0
3789 653 1
653 208 1
208 3614 0
3614 1561 1
1561 1997 0
1997 973 1
973 365 0
365 609 0
609 1671 1
1671 1593 0
1593 2676 1
2676 1147 0
1147 ...

output:

794220612

result:

ok single line: '794220612'

Test #37:

score: 24

Accepted

time: 623ms

memory: 180628kb

input:

3962 9999 8
1 2711 0
2711 3474 1
3474 2084 0
2084 1854 0
1854 3779 1
3779 2180 0
2180 3507 0
3507 2960 1
2960 955 0
955 2600 0
2600 1585 0
1585 617 0
617 623 0
623 94 1
94 211 0
211 3649 1
3649 3123 1
3123 166 0
166 213 0
213 568 0
568 2679 1
2679 3588 1
3588 3800 1
3800 3033 1
3033 1170 1
1170 802 ...

output:

588441215

result:

ok single line: '588441215'

Test #38:

score: 24

Accepted

time: 52ms

memory: 28724kb

input:

201 7584 8
2 2 2
2 201 1
3 3 3
3 201 1
4 4 4
4 201 2
4 201 3
5 5 5
5 201 4
6 6 6
6 201 3
6 201 5
7 7 7
7 201 1
7 201 4
7 201 6
8 8 8
8 201 0
8 201 2
8 201 3
8 201 4
9 9 9
9 201 0
9 201 2
9 201 5
9 201 6
9 201 7
10 10 10
10 201 1
10 201 2
10 201 4
10 201 8
11 11 11
11 201 0
11 201 3
11 201 4
12 12 12...

output:

result:

ok single line: '1'

Test #39:

score: 24

Accepted

time: 65ms

memory: 24652kb

input:

output:

670693521

result:

ok single line: '670693521'

Test #40:

score: 24

Accepted

time: 34ms

memory: 24416kb

input:

output:

980169960

result:

ok single line: '980169960'

Test #41:

score: 24

Accepted

time: 59ms

memory: 24368kb

input:

output:

700368949

result:

ok single line: '700368949'

Test #42:

score: 24

Accepted

time: 284ms

memory: 180664kb

input:

3962 5398 8
1 1387 0
1387 3656 1
3656 1250 1
1250 128 0
128 1202 0
1202 83 1
83 90 0
90 1218 0
1218 656 0
656 565 1
565 3670 1
3670 289 0
289 239 0
239 1109 1
1109 2050 0
2050 3844 1
3844 52 0
52 1562 1
1562 3686 0
3686 2596 1
2596 3035 0
3035 1365 0
1365 943 1
943 954 1
954 560 0
560 1204 0
1204 52...

output:

338765692

result:

ok single line: '338765692'

Test #43:

score: 24

Accepted

time: 398ms

memory: 217544kb

input:

4952 8000 8
1 2814 1
2814 3322 0
3322 3360 1
3360 1222 0
1222 4598 0
4598 4852 1
4852 3052 0
3052 663 1
663 3644 1
3644 4410 0
4410 4229 1
4229 4222 1
4222 217 1
217 2528 1
2528 1136 0
1136 2144 0
2144 1118 1
1118 323 0
323 1006 1
1006 3215 0
3215 3497 1
3497 3463 1
3463 2405 0
2405 456 0
456 4819 1...

output:

result:

ok single line: '660'

Test #44:

score: 24

Accepted

time: 368ms

memory: 217592kb

input:

4952 7588 8
1 511 0
511 4170 1
4170 1735 1
1735 2956 0
2956 2305 0
2305 4126 0
4126 4565 1
4565 2701 0
2701 766 1
766 759 0
759 1530 0
1530 1952 0
1952 752 1
752 677 0
677 2739 0
2739 149 1
149 2113 0
2113 4945 0
4945 3902 1
3902 2552 1
2552 4907 0
4907 2271 1
2271 4658 0
4658 1200 0
1200 2176 1
217...

output:

13712160

result:

ok single line: '13712160'

Test #45:

score: 24

Accepted

time: 4ms

memory: 203348kb

input:

5000 10000 8
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

result:

ok single line: '4'

Test #46:

score: 24

Accepted

time: 537ms

memory: 217384kb

input:

4951 10000 8
2 3 1
3 2 1
4 5 1
5 6 1
6 4 1
7 8 1
8 9 1
9 10 1
10 7 1
11 12 1
12 13 1
13 14 1
14 15 1
15 11 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 16 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 22 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 29 1
37 38 1
38 39 1
39 40 1...

output:

result:

ok single line: '1'

Test #47:

score: 24

Accepted

time: 62ms

memory: 26484kb

input:

output:

837484870

result:

ok single line: '837484870'

Test #48:

score: 24

Accepted

time: 390ms

memory: 217512kb

input:

4952 7334 8
1 3824 0
3824 480 1
480 444 0
444 637 0
637 2312 1
2312 3356 0
3356 4210 1
4210 2721 1
2721 4781 0
4781 3785 1
3785 357 0
357 3055 0
3055 1686 0
1686 2951 0
2951 4331 0
4331 1313 1
1313 3564 1
3564 3337 0
3337 3344 1
3344 3667 0
3667 1044 0
1044 3490 1
3490 4907 0
4907 1070 0
1070 1737 1...

output:

117674516

result:

ok single line: '117674516'

Test #49:

score: 24

Accepted

time: 389ms

memory: 215972kb

input:

4952 7370 8
1 2579 1
2579 1964 1
1964 1371 1
1371 2599 0
2599 804 0
804 4618 0
4618 3004 1
3004 4230 1
4230 3411 0
3411 3143 0
3143 2458 0
2458 4734 1
4734 4628 0
4628 3284 1
3284 269 0
269 1978 0
1978 910 0
910 1989 1
1989 2327 0
2327 4011 0
4011 293 1
293 182 1
182 1070 1
1070 4505 1
4505 4870 0
4...

output:

308689785

result:

ok single line: '308689785'

Test #50:

score: 24

Accepted

time: 382ms

memory: 217432kb

input:

4952 7319 8
1 1538 0
1538 4513 0
4513 4932 0
4932 961 0
961 3337 1
3337 3413 1
3413 1373 1
1373 2702 0
2702 4299 1
4299 4938 0
4938 3207 0
3207 4694 0
4694 610 1
610 2244 1
2244 633 0
633 4800 1
4800 1007 1
1007 769 0
769 870 0
870 1555 0
1555 4758 1
4758 2327 0
2327 892 0
892 4187 0
4187 4823 0
482...

output:

506483589

result:

ok single line: '506483589'

Test #51:

score: 24

Accepted

time: 18ms

memory: 22540kb

input:

output:

result:

ok single line: '27'

Test #52:

score: 24

Accepted

time: 28ms

memory: 28412kb

input:

output:

result:

ok single line: '1728'

Test #53:

score: 24

Accepted

time: 370ms

memory: 217536kb

input:

4952 7041 8
1 59 0
59 3267 1
3267 281 0
281 1741 0
1741 661 0
661 353 1
353 1581 0
1581 2179 0
2179 170 0
170 2693 1
2693 440 0
440 3281 1
3281 3177 1
3177 4515 1
4515 3680 1
3680 4205 0
4205 216 1
216 2913 1
2913 4872 1
4872 3483 0
3483 2286 0
2286 1877 0
1877 4743 0
4743 2441 0
2441 3266 0
3266 12...

output:

result:

ok single line: '5400'

Test #54:

score: 24

Accepted

time: 34ms

memory: 22364kb

input:

output:

243354720

result:

ok single line: '243354720'

Test #55:

score: 24

Accepted

time: 64ms

memory: 24364kb

input:

output:

604422963

result:

ok single line: '604422963'

Extra Test:

score: 0

Extra Test Passed