QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#664163#9491. 生命的循环275307894a100 ✓725ms37548kbC++144.7kb2024-10-21 19:26:062024-10-21 19:26:08

Judging History

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

  • [2024-10-21 19:26:08]
  • 评测
  • 测评结果:100
  • 用时:725ms
  • 内存:37548kb
  • [2024-10-21 19:26:06]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5000+5,M=N*120+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,type,k;
int X[N*2],Y[N*2],Z[N*2];
vector<int> S[N];
int scc[N];
namespace Tarjan{
	int dfn[N],low[N],dh,st[N],sh;
	void tarjan(int x){
		dfn[x]=low[x]=++dh;st[++sh]=x;
		for(int i:S[x]){
			if(!dfn[i]) tarjan(i),low[x]=min(low[x],low[i]);
			else if(!scc[i]) low[x]=min(low[x],dfn[i]);
		}
		if(low[x]==dfn[x]){
			++k;
			while(st[sh+1]^x) scc[st[sh]]=k,sh--;	
		}
	}
	void build(){
		for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	}
}
vector<int> V[N],G1[N],G2[N];
bitset<101> g1[N][101],g2[N][101];
int w[N];
int qryGCD(int x){
	static int dis[N];
	for(int i=101;i;i--){
		for(int j:V[x]) dis[j]=-1;
		dis[V[x][0]]=0;
		queue<int> q;
		q.push(V[x][0]);
		int flag=0;
		while(!q.empty()){
			int x=q.front();q.pop();
			for(int j:G1[x]){
				int y=Y[j];
				if(~dis[y]){
					if(dis[y]!=(dis[x]+Z[j])%i) {flag=1;break;}
				}else dis[y]=(dis[x]+Z[j])%i,q.push(y);
			}
		}
		if(!flag) return i;
	}
	return 0;
}
void dfs1(int x,int a,int b){
	if(g1[x][a][b]) return;
	g1[x][a][b]=1;
	for(int i:G2[x]) dfs1(Y[i],a,(b+Z[i])%a);
}
void dfs2(int x,int a,int b){
	if(w[scc[x]]^101) a=__gcd(a,w[scc[x]]),b%=a;
	if(g2[x][a][b]) return;
	g2[x][a][b]=1;
	for(int i:G2[x]) dfs2(Y[i],a,(b+Z[i])%a);
}
namespace BigInt{
	int k,ans[N];
	void init(){
		k=0;ans[0]=1;
	}
	void mul(int x){
		int w=0;
		for(int i=k;~i;i--) w=(w*10+ans[i])%x;
		x/=__gcd(w,x);
		for(int i=0;i<=k;i++) ans[i]*=x;
		for(int i=0;i<k;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
		while(ans[k]>=10) ans[k+1]=ans[k]/10,ans[k]%=10,k++;
	}
	void print(){
		ll w=0;
		const int mod=1e9+9;
		for(int i=k;~i;i--) w=(w*10+ans[i])%mod;
		printf("%lld\n",w);
	}
}
bitset<105> g[105],vis[105],f[105],msk;
const int I=32*27*5*7;
int G[N];
void Solve(){
	scanf("%d%d%d",&n,&m,&type);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
		S[X[i]].push_back(Y[i]);
	}
	Tarjan::build();
	for(int i=1;i<=m;i++){
		if(scc[X[i]]==scc[Y[i]]) G1[X[i]].push_back(i);
		G2[X[i]].push_back(i);
	}
	for(int i=1;i<=n;i++) V[scc[i]].push_back(i);
	for(int i=1;i<=k;i++) w[i]=qryGCD(i);
	for(int i=1;i<=100;i++) dfs1(1,i,0);
	for(int i=1;i<=n;i++) if(w[scc[i]]^101){
		for(int y=0;y<w[scc[i]];y++) if(g1[i][w[scc[i]]][y]) dfs2(i,w[scc[i]],y);
	}
	BigInt::init();
	for(int x=1;x<=100;x++) for(int y=0;y<x;y++) g[x][y]=g2[n][x][y];
	for(int x=1;x<=100;x++) G[x]=__gcd(I,x);
	for(int i=0;i<I;i++){
		int flag=0;
		for(int x=1;x<=100;x++) f[x].set();
		for(int x=1;x<=100;x++){
			int w=G[x];
			if(x==w){
				if(g[x][i%w]){flag=1;break;}
				continue;
			}
			msk.reset();
			for(int y=i%w;y<x;y+=w)if(!g[x][y]) msk.set(y%(x/w));
			f[x/w]&=msk;
		}
		for(int x=1;x<=100;x++) if(!f[x].count()) flag=1;
		if(flag) continue;
		for(int x=1;x<=100;x++){
			int w=G[x];
			if(x==w){
				vis[x].set(i%w);
				continue;
			}
			for(int y=i%w;y<x;y+=w) if(f[x/w][y%(x/w)]) vis[x].set(y);
		}
	}
	for(int x=1;x<=100;x++){
		for(int y=0;y<x;y++) if(!vis[x][y]) g[x][y]=1;
		vis[x].reset();
	}
	for(int x=1;x<=100;x++){
		for(int y=0;y<x;y++) if(g[x][y]){
			for(int z=2;x*z<=100;z++){
				for(int b=y;b<x*z;b+=x) g[x*z][b]=1,vis[x*z][b]=1;
			}
		}
	}
	for(int x=100;x;x--){
		for(int y=0;y<x;y++)if(!g[x][y]){
			for(int z=2;x*z<=100;z++){
				int flag=0;
				for(int b=y;b<x*z;b+=x) if(!g[x*z][b]) flag=1;
				if(!flag){
					g[x][y]=1;
					for(int b=y;b<x*z;b+=x) vis[x*z][b]=1;
				}
			}
		}
	}
	for(int x=100;x;x--){
		for(int y=0;y<x;y++) if(!vis[x][y]&&g[x][y]){gdb(x);BigInt::mul(x);break;}
	}
	// for(int i=1;;i++) if(604422963ll*i%mod==208845917) gdb(i);
	BigInt::print();
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 275ms
memory: 6520kb

input:

30 2000 1
9 19 58
20 17 5
20 17 96
27 20 2
15 28 71
14 18 20
19 24 29
18 13 66
21 17 62
20 17 86
23 20 58
18 26 69
29 18 73
30 26 13
27 17 73
23 15 30
10 8 68
25 6 51
7 4 55
23 13 74
12 8 94
23 29 33
6 8 86
1 8 75
14 30 73
23 27 82
14 26 85
12 28 68
1 27 21
6 8 74
22 13 61
17 5 58
28 3 69
1 25 59
11...

output:

1

result:

ok single line: '1'

Test #2:

score: 1
Accepted
time: 254ms
memory: 5068kb

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:

1

result:

ok single line: '1'

Subtask #2:

score: 8
Accepted

Test #3:

score: 8
Accepted
time: 136ms
memory: 4544kb

input:

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

output:

2

result:

ok single line: '2'

Test #4:

score: 8
Accepted
time: 168ms
memory: 6008kb

input:

7 11 2
1 2 1
2 3 3
3 2 5
2 7 1
3 7 2
1 5 3
5 5 6
5 7 1
1 6 2
6 6 10
6 7 4

output:

60

result:

ok single line: '60'

Test #5:

score: 8
Accepted
time: 141ms
memory: 6000kb

input:

7 15 2
1 2 1
2 2 8
2 7 10
1 3 8
3 3 3
3 7 2
1 4 8
4 4 10
4 7 6
1 5 3
5 5 9
5 7 4
1 6 4
6 6 6
6 7 0

output:

120

result:

ok single line: '120'

Subtask #3:

score: 11
Accepted

Test #6:

score: 11
Accepted
time: 447ms
memory: 23240kb

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:

14

result:

ok single line: '14'

Test #7:

score: 11
Accepted
time: 311ms
memory: 12904kb

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:

48

result:

ok single line: '48'

Test #8:

score: 11
Accepted
time: 283ms
memory: 5540kb

input:

100 7000 3
11 14 0
41 73 0
58 2 0
85 30 0
69 59 0
3 84 0
55 87 0
50 66 0
37 89 0
25 100 0
100 63 0
73 30 0
79 83 0
3 84 0
25 28 0
51 57 0
79 47 0
55 19 0
60 68 0
42 53 0
36 47 0
76 32 0
60 78 0
65 71 0
73 15 0
7 61 0
31 19 0
92 32 0
74 21 0
7 43 0
21 56 0
66 5 0
34 88 0
95 5 0
25 55 0
54 88 0
44 97 ...

output:

3

result:

ok single line: '3'

Subtask #4:

score: 10
Accepted

Dependency #3:

100%
Accepted

Test #9:

score: 10
Accepted
time: 411ms
memory: 24320kb

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:

30

result:

ok single line: '30'

Test #10:

score: 10
Accepted
time: 504ms
memory: 13616kb

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:

12

result:

ok single line: '12'

Subtask #5:

score: 19
Accepted

Test #11:

score: 19
Accepted
time: 271ms
memory: 8196kb

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:

1

result:

ok single line: '1'

Test #12:

score: 19
Accepted
time: 119ms
memory: 4752kb

input:

26 638 5
1 2 0
2 2 72
2 26 0
2 26 1
2 26 6
2 26 7
2 26 12
2 26 13
2 26 18
2 26 19
2 26 24
2 26 25
2 26 30
2 26 31
2 26 36
2 26 37
2 26 42
2 26 43
2 26 48
2 26 49
2 26 54
2 26 55
2 26 60
2 26 61
2 26 66
2 26 67
1 3 0
3 3 25
3 26 0
3 26 1
3 26 2
3 26 3
3 26 5
3 26 6
3 26 7
3 26 8
3 26 10
3 26 11
3 26 ...

output:

381798563

result:

ok single line: '381798563'

Test #13:

score: 19
Accepted
time: 165ms
memory: 4580kb

input:

25 628 5
1 2 0
2 2 90
2 25 0
2 25 2
2 25 5
2 25 6
2 25 7
2 25 8
2 25 10
2 25 11
2 25 12
2 25 14
2 25 17
2 25 18
2 25 19
2 25 21
2 25 26
2 25 27
2 25 28
2 25 29
2 25 30
2 25 32
2 25 35
2 25 36
2 25 37
2 25 38
2 25 40
2 25 41
2 25 42
2 25 44
2 25 47
2 25 48
2 25 49
2 25 51
2 25 56
2 25 57
2 25 58
2 25...

output:

672589923

result:

ok single line: '672589923'

Test #14:

score: 19
Accepted
time: 99ms
memory: 4844kb

input:

127 5541 5
2 2 2
2 127 0
2 127 1
3 3 3
3 127 0
3 127 2
4 4 5
4 127 0
4 127 2
5 5 7
5 127 0
5 127 1
5 127 2
5 127 4
5 127 5
5 127 6
6 6 11
6 127 1
6 127 2
6 127 4
6 127 6
6 127 7
6 127 9
7 7 13
7 127 8
8 8 17
8 127 0
8 127 1
8 127 4
8 127 6
8 127 8
8 127 10
8 127 12
8 127 13
8 127 15
8 127 16
9 9 19
...

output:

1

result:

ok single line: '1'

Test #15:

score: 19
Accepted
time: 67ms
memory: 4564kb

input:

20 396 5
1 2 0
2 2 2
1 3 0
3 3 3
3 20 0
3 20 1
1 4 0
4 4 7
4 20 0
4 20 4
4 20 6
1 5 0
5 5 11
5 20 0
5 20 4
5 20 5
5 20 6
5 20 7
5 20 9
1 6 0
6 6 13
6 20 2
6 20 3
6 20 5
6 20 7
6 20 9
1 7 0
7 7 19
7 20 0
7 20 2
7 20 3
7 20 6
7 20 7
7 20 8
7 20 12
7 20 13
7 20 14
7 20 15
7 20 16
7 20 18
1 8 0
8 8 23
8...

output:

868803081

result:

ok single line: '868803081'

Subtask #6:

score: 9
Accepted

Test #16:

score: 9
Accepted
time: 58ms
memory: 4592kb

input:

25 596 6
1 2 0
2 2 16
2 25 2
2 25 4
2 25 5
2 25 6
2 25 7
2 25 8
2 25 9
2 25 10
2 25 11
2 25 12
2 25 13
2 25 14
1 3 0
3 3 64
3 25 0
3 25 1
3 25 2
3 25 6
3 25 7
3 25 8
3 25 9
3 25 10
3 25 14
3 25 15
3 25 16
3 25 17
3 25 18
3 25 22
3 25 23
3 25 24
3 25 25
3 25 26
3 25 30
3 25 31
3 25 32
3 25 33
3 25 34...

output:

7398268

result:

ok single line: '7398268'

Test #17:

score: 9
Accepted
time: 35ms
memory: 4480kb

input:

8 71 6
1 2 0
2 2 2
1 3 0
3 3 4
3 8 0
3 8 1
3 8 2
1 4 0
4 4 8
4 8 3
4 8 4
1 5 0
5 5 16
5 8 1
5 8 3
5 8 4
5 8 5
5 8 6
5 8 8
5 8 10
5 8 11
5 8 13
5 8 14
5 8 15
1 6 0
6 6 32
6 8 1
6 8 2
6 8 3
6 8 4
6 8 6
6 8 10
6 8 11
6 8 12
6 8 14
6 8 18
6 8 19
6 8 20
6 8 22
6 8 26
6 8 27
6 8 28
6 8 31
1 7 0
7 7 64
7 8...

output:

16

result:

ok single line: '16'

Test #18:

score: 9
Accepted
time: 85ms
memory: 6188kb

input:

14 189 6
1 2 0
2 2 3
1 3 0
3 3 7
3 14 2
3 14 5
3 14 6
1 4 0
4 4 8
4 14 0
4 14 2
4 14 7
1 5 0
5 5 11
5 14 2
5 14 6
1 6 0
6 6 25
6 14 2
6 14 3
6 14 4
6 14 7
6 14 8
6 14 9
6 14 12
6 14 13
6 14 14
6 14 18
6 14 19
6 14 22
6 14 23
6 14 24
1 7 0
7 7 29
7 14 2
7 14 3
7 14 4
7 14 7
7 14 11
7 14 13
7 14 16
7 ...

output:

714737421

result:

ok single line: '714737421'

Test #19:

score: 9
Accepted
time: 266ms
memory: 10500kb

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:

1

result:

ok single line: '1'

Test #20:

score: 9
Accepted
time: 725ms
memory: 37308kb

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:

9

result:

ok single line: '9'

Subtask #7:

score: 18
Accepted

Test #21:

score: 18
Accepted
time: 21ms
memory: 6132kb

input:

15 133 7
1 2 0
2 2 5
2 15 1
2 15 3
2 15 4
1 3 0
3 3 8
3 15 2
3 15 3
3 15 6
1 4 0
4 4 9
4 15 3
4 15 4
4 15 5
4 15 7
1 5 0
5 5 10
5 15 2
5 15 4
5 15 6
5 15 7
5 15 8
5 15 9
1 6 0
6 6 12
6 15 2
6 15 4
6 15 5
6 15 9
6 15 10
6 15 11
1 7 0
7 7 13
7 15 0
7 15 1
7 15 2
7 15 3
7 15 5
7 15 6
7 15 7
7 15 9
7 15...

output:

1

result:

ok single line: '1'

Test #22:

score: 18
Accepted
time: 23ms
memory: 6320kb

input:

15 123 7
1 2 0
2 2 5
2 15 0
2 15 3
2 15 4
1 3 0
3 3 6
3 15 0
3 15 3
3 15 5
1 4 0
4 4 7
4 15 1
4 15 2
4 15 4
4 15 6
1 5 0
5 5 9
5 15 0
5 15 1
5 15 2
5 15 5
5 15 6
5 15 8
1 6 0
6 6 10
6 15 1
6 15 3
6 15 4
6 15 5
6 15 8
6 15 9
1 7 0
7 7 13
7 15 0
7 15 2
7 15 12
1 8 0
8 8 15
8 15 0
8 15 1
8 15 2
8 15 3
...

output:

3063060

result:

ok single line: '3063060'

Test #23:

score: 18
Accepted
time: 22ms
memory: 4480kb

input:

11 89 7
1 2 0
2 2 5
2 11 1
2 11 3
2 11 4
1 3 0
3 3 8
3 11 0
3 11 2
3 11 3
3 11 4
3 11 6
1 4 0
4 4 9
4 11 0
4 11 1
4 11 2
4 11 5
4 11 7
1 5 0
5 5 12
5 11 1
5 11 3
5 11 7
5 11 8
5 11 10
5 11 11
1 6 0
6 6 14
6 11 0
6 11 3
6 11 4
6 11 6
6 11 7
6 11 8
6 11 9
6 11 13
1 7 0
7 7 19
7 11 0
7 11 3
7 11 4
7 11...

output:

3423420

result:

ok single line: '3423420'

Test #24:

score: 18
Accepted
time: 30ms
memory: 4540kb

input:

13 89 5
1 2 0
2 2 4
2 13 3
1 3 0
3 3 6
3 13 1
3 13 2
3 13 3
3 13 5
1 4 0
4 4 7
4 13 1
4 13 4
4 13 6
1 5 0
5 5 9
5 13 0
5 13 1
5 13 2
5 13 4
5 13 5
5 13 7
1 6 0
6 6 10
6 13 1
6 13 2
6 13 4
6 13 5
1 7 0
7 7 11
7 13 1
7 13 3
7 13 4
7 13 8
1 8 0
8 8 13
8 13 0
8 13 1
8 13 3
8 13 4
8 13 8
8 13 10
8 13 11
...

output:

346393023

result:

ok single line: '346393023'

Test #25:

score: 18
Accepted
time: 22ms
memory: 4540kb

input:

14 122 7
1 2 0
2 2 4
2 14 1
2 14 2
2 14 3
1 3 0
3 3 6
3 14 0
3 14 4
1 4 0
4 4 7
4 14 1
4 14 2
4 14 3
1 5 0
5 5 9
5 14 1
5 14 2
5 14 3
5 14 8
1 6 0
6 6 10
6 14 1
6 14 2
6 14 3
6 14 6
6 14 7
6 14 9
1 7 0
7 7 15
7 14 0
7 14 2
7 14 4
7 14 5
7 14 6
7 14 7
7 14 9
7 14 11
7 14 13
7 14 14
1 8 0
8 8 17
8 14 ...

output:

528923553

result:

ok single line: '528923553'

Test #26:

score: 18
Accepted
time: 29ms
memory: 4548kb

input:

10 62 7
1 2 0
2 2 4
2 10 1
2 10 2
2 10 3
1 3 0
3 3 5
3 10 1
1 4 0
4 4 6
4 10 1
4 10 3
4 10 4
1 5 0
5 5 9
5 10 0
5 10 3
5 10 4
5 10 6
5 10 7
1 6 0
6 6 11
6 10 1
6 10 2
6 10 4
6 10 5
6 10 6
6 10 7
6 10 8
6 10 9
1 7 0
7 7 17
7 10 0
7 10 2
7 10 3
7 10 4
7 10 5
7 10 8
7 10 9
7 10 11
7 10 13
7 10 14
1 8 0...

output:

1492260

result:

ok single line: '1492260'

Test #27:

score: 18
Accepted
time: 694ms
memory: 34416kb

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:

3

result:

ok single line: '3'

Test #28:

score: 18
Accepted
time: 26ms
memory: 4632kb

input:

31 465 7
1 2 0
2 2 2
1 3 0
3 3 3
3 31 0
3 31 1
1 4 0
4 4 4
4 31 1
4 31 2
1 5 0
5 5 5
5 31 0
5 31 2
5 31 4
1 6 0
6 6 6
6 31 0
6 31 1
6 31 3
6 31 4
1 7 0
7 7 7
7 31 1
7 31 2
7 31 3
7 31 4
7 31 5
1 8 0
8 8 8
8 31 1
8 31 2
8 31 4
8 31 5
8 31 6
8 31 7
1 9 0
9 9 9
9 31 0
9 31 1
9 31 3
9 31 4
9 31 5
9 31 6...

output:

89541839

result:

ok single line: '89541839'

Test #29:

score: 18
Accepted
time: 26ms
memory: 4604kb

input:

31 451 7
1 2 0
2 2 2
2 31 1
1 3 0
3 3 3
3 31 0
3 31 2
1 4 0
4 4 4
4 31 0
4 31 1
4 31 3
1 5 0
5 5 5
5 31 0
5 31 1
5 31 2
5 31 3
1 6 0
6 6 6
6 31 0
6 31 1
6 31 2
6 31 3
6 31 5
1 7 0
7 7 7
7 31 0
7 31 2
7 31 3
7 31 4
7 31 5
1 8 0
8 8 8
8 31 0
8 31 1
8 31 3
8 31 4
8 31 5
8 31 6
8 31 7
1 9 0
9 9 9
9 31 0...

output:

160733989

result:

ok single line: '160733989'

Test #30:

score: 18
Accepted
time: 24ms
memory: 4432kb

input:

17 140 7
1 2 0
2 2 2
2 17 0
1 3 0
3 3 4
3 17 3
1 4 0
4 4 5
1 5 0
5 5 7
5 17 0
5 17 3
5 17 4
1 6 0
6 6 9
6 17 0
6 17 2
6 17 3
6 17 6
6 17 8
1 7 0
7 7 13
7 17 1
7 17 2
7 17 4
7 17 7
7 17 9
7 17 10
1 8 0
8 8 17
8 17 1
8 17 2
8 17 7
8 17 8
8 17 9
8 17 12
8 17 13
8 17 14
8 17 15
1 9 0
9 9 18
9 17 1
9 17 ...

output:

767157300

result:

ok single line: '767157300'

Test #31:

score: 18
Accepted
time: 23ms
memory: 4728kb

input:

20 186 7
1 2 0
2 2 2
1 3 0
3 3 4
3 20 0
3 20 3
1 4 0
4 4 5
4 20 1
4 20 4
1 5 0
5 5 8
5 20 3
5 20 5
5 20 6
1 6 0
6 6 10
6 20 1
6 20 2
6 20 3
6 20 4
6 20 8
1 7 0
7 7 13
7 20 0
7 20 1
7 20 2
7 20 4
7 20 5
7 20 8
7 20 10
1 8 0
8 8 14
8 20 1
8 20 2
8 20 6
8 20 8
8 20 12
1 9 0
9 9 17
9 20 4
9 20 5
9 20 11...

output:

362040671

result:

ok single line: '362040671'

Test #32:

score: 18
Accepted
time: 20ms
memory: 6300kb

input:

9 75 7
1 2 0
2 2 7
2 9 1
2 9 2
2 9 4
1 3 0
3 3 8
3 9 3
3 9 4
3 9 5
3 9 6
3 9 7
1 4 0
4 4 10
4 9 1
4 9 3
4 9 7
1 5 0
5 5 17
5 9 2
5 9 4
5 9 5
5 9 8
5 9 12
5 9 15
5 9 16
1 6 0
6 6 18
6 9 0
6 9 1
6 9 2
6 9 3
6 9 4
6 9 6
6 9 8
6 9 9
6 9 10
6 9 12
6 9 14
6 9 16
1 7 0
7 7 24
7 9 0
7 9 1
7 9 2
7 9 3
7 9 6
...

output:

414120

result:

ok single line: '414120'

Test #33:

score: 18
Accepted
time: 116ms
memory: 9476kb

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:

7020

result:

ok single line: '7020'

Test #34:

score: 18
Accepted
time: 96ms
memory: 9468kb

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:

9828

result:

ok single line: '9828'

Test #35:

score: 18
Accepted
time: 327ms
memory: 21688kb

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: 240ms
memory: 19220kb

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: 249ms
memory: 17632kb

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: 109ms
memory: 4924kb

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:

1

result:

ok single line: '1'

Test #39:

score: 24
Accepted
time: 39ms
memory: 8128kb

input:

14 345 8
1 2 0
2 2 5
1 3 0
3 3 6
3 14 0
3 14 1
3 14 2
3 14 5
1 4 0
4 4 20
4 14 0
4 14 1
4 14 2
4 14 4
4 14 5
4 14 10
4 14 11
4 14 13
4 14 15
4 14 16
4 14 17
4 14 19
1 5 0
5 5 34
5 14 1
5 14 2
5 14 4
5 14 5
5 14 8
5 14 9
5 14 10
5 14 11
5 14 13
5 14 20
5 14 21
5 14 22
5 14 23
5 14 25
5 14 26
5 14 28
...

output:

670693521

result:

ok single line: '670693521'

Test #40:

score: 24
Accepted
time: 32ms
memory: 8212kb

input:

12 249 8
1 2 0
2 2 15
1 3 0
3 3 24
3 12 0
3 12 2
3 12 5
3 12 6
3 12 9
3 12 10
3 12 11
3 12 14
3 12 15
3 12 17
3 12 18
3 12 20
3 12 21
3 12 22
1 4 0
4 4 28
4 12 1
4 12 2
4 12 3
4 12 4
4 12 5
4 12 6
4 12 7
4 12 9
4 12 10
4 12 11
4 12 12
4 12 13
4 12 14
4 12 15
4 12 16
4 12 17
4 12 18
4 12 19
4 12 20
4...

output:

980169960

result:

ok single line: '980169960'

Test #41:

score: 24
Accepted
time: 44ms
memory: 6272kb

input:

16 261 8
1 2 0
2 2 2
2 16 0
1 3 0
3 3 4
1 4 0
4 4 15
4 16 1
4 16 4
4 16 7
4 16 10
4 16 13
1 5 0
5 5 17
5 16 1
5 16 3
5 16 5
5 16 6
5 16 7
5 16 9
5 16 10
5 16 14
5 16 15
1 6 0
6 6 21
6 16 3
6 16 4
6 16 6
6 16 7
6 16 12
6 16 13
6 16 14
6 16 15
6 16 16
6 16 17
1 7 0
7 7 38
7 16 1
7 16 4
7 16 6
7 16 7
7...

output:

700368949

result:

ok single line: '700368949'

Test #42:

score: 24
Accepted
time: 199ms
memory: 17708kb

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: 274ms
memory: 21088kb

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:

660

result:

ok single line: '660'

Test #44:

score: 24
Accepted
time: 278ms
memory: 21332kb

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: 658ms
memory: 37548kb

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:

4

result:

ok single line: '4'

Test #46:

score: 24
Accepted
time: 338ms
memory: 18700kb

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:

1

result:

ok single line: '1'

Test #47:

score: 24
Accepted
time: 27ms
memory: 4540kb

input:

13 334 8
1 2 0
2 2 10
2 13 0
2 13 1
2 13 2
2 13 3
2 13 5
2 13 6
2 13 7
2 13 9
1 3 0
3 3 15
3 13 0
3 13 3
3 13 4
3 13 5
3 13 7
3 13 8
3 13 9
3 13 14
1 4 0
4 4 21
4 13 0
4 13 1
4 13 2
4 13 3
4 13 7
4 13 12
4 13 13
4 13 14
4 13 16
4 13 17
1 5 0
5 5 23
5 13 3
5 13 5
5 13 6
5 13 7
5 13 9
5 13 10
5 13 11
...

output:

837484870

result:

ok single line: '837484870'

Test #48:

score: 24
Accepted
time: 264ms
memory: 21012kb

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: 261ms
memory: 21008kb

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: 272ms
memory: 21204kb

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: 70ms
memory: 6000kb

input:

6 58 8
1 2 0
2 2 3
2 6 0
1 3 0
3 3 9
3 6 3
3 6 4
3 6 7
1 4 0
4 4 27
4 6 3
4 6 10
4 6 14
4 6 15
4 6 16
4 6 19
4 6 20
4 6 21
4 6 23
4 6 25
1 5 0
5 5 81
5 6 0
5 6 3
5 6 4
5 6 8
5 6 9
5 6 10
5 6 12
5 6 13
5 6 17
5 6 18
5 6 21
5 6 22
5 6 26
5 6 27
5 6 30
5 6 35
5 6 36
5 6 39
5 6 40
5 6 44
5 6 45
5 6 48
5...

output:

27

result:

ok single line: '27'

Test #52:

score: 24
Accepted
time: 23ms
memory: 4496kb

input:

12 158 8
1 2 0
2 2 3
2 12 0
2 12 2
1 3 0
3 3 9
3 12 3
3 12 6
3 12 8
1 4 0
4 4 27
4 12 1
4 12 4
4 12 5
4 12 8
4 12 12
4 12 14
4 12 16
4 12 17
4 12 19
4 12 20
4 12 22
4 12 25
1 5 0
5 5 81
5 12 0
5 12 1
5 12 3
5 12 4
5 12 5
5 12 6
5 12 9
5 12 10
5 12 12
5 12 13
5 12 14
5 12 15
5 12 18
5 12 19
5 12 21
5...

output:

1728

result:

ok single line: '1728'

Test #53:

score: 24
Accepted
time: 252ms
memory: 20916kb

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:

5400

result:

ok single line: '5400'

Test #54:

score: 24
Accepted
time: 22ms
memory: 4492kb

input:

10 186 8
1 2 0
2 2 7
2 10 0
2 10 1
2 10 2
2 10 3
2 10 4
2 10 6
1 3 0
3 3 10
3 10 0
3 10 1
3 10 2
3 10 3
3 10 4
3 10 5
3 10 8
3 10 9
1 4 0
4 4 30
4 10 0
4 10 1
4 10 3
4 10 4
4 10 5
4 10 7
4 10 8
4 10 9
4 10 11
4 10 13
4 10 14
4 10 16
4 10 17
4 10 21
4 10 22
4 10 24
4 10 25
4 10 26
4 10 27
4 10 28
4 1...

output:

243354720

result:

ok single line: '243354720'

Test #55:

score: 24
Accepted
time: 103ms
memory: 6516kb

input:

12 322 8
1 2 0
2 2 19
2 12 1
2 12 3
2 12 4
2 12 5
2 12 7
2 12 9
2 12 10
2 12 12
2 12 15
2 12 16
2 12 18
1 3 0
3 3 43
3 12 8
3 12 10
3 12 18
3 12 40
1 4 0
4 4 44
4 12 0
4 12 1
4 12 3
4 12 4
4 12 5
4 12 6
4 12 7
4 12 8
4 12 9
4 12 10
4 12 14
4 12 15
4 12 18
4 12 19
4 12 21
4 12 22
4 12 23
4 12 25
4 12...

output:

604422963

result:

ok single line: '604422963'

Extra Test:

score: 0
Extra Test Passed