QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#879914	#8947. 白兔迷宫	liulianll	32	24ms	4736kb	C++14	2.1kb	2025-02-02 17:54:07	2025-02-02 17:54:07

Judging History

This is the latest submission verdict.

[2025-02-02 17:54:07]
Judged

Verdict: 32
Time: 24ms
Memory: 4736kb

Show

[2025-02-02 17:54:07]
Submitted

answer

#include<bits/stdc++.h>
#define mod 998244353
#define inv(x) (fastpow(x,mod-2))
using namespace std;
int n,m,s,t,u,v,o,cnt;
struct Line{
	int u,v,o;
}line[10010];
long long f[110],g[110],h[110],a[310][310],x[310],deg[110],d[110];
long long fastpow(long long x,long long y){
	long long ans=1;
	while(y){
		if(y&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return ans;
}
void solve(int p,int q,int n,int m){
	if(p>n||q>n){
		for(int i=1;i<=n;i++){
			x[i]=a[i][n+1]*inv(a[i][i]);
		}
		return;
	}
	int k=0;
	for(int i=p;i<=n;i++){
		if(a[i][q]){
			k=i;break;
		}
	}
	for(int i=1;i<=m;i++){
		swap(a[p][i],a[k][i]);
	}
	for(int i=1;i<=n;i++){
		long long v=a[i][q]*inv(a[p][q]);
		if(a[i][q]!=0&&i!=p){
			for(int j=m;j>=q;j--){
				a[i][j]=((a[i][j]-(a[p][j]*v))%mod+mod)%mod;
			}
		}
	}
	solve(p+1,q+1,n,m);
	return;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&u,&v,&o);
		if(u==t) continue;
		line[++cnt].o=o;
		line[cnt].u=u;
		line[cnt].v=v;
		++deg[u];
	}
	m=cnt;
	a[s][3*n+1]=1;
	for(int i=1;i<=n;++i){
		d[i]=inv(deg[i]);
	}
	for(int i=1;i<=3*n;++i) ++a[i][i];
	for(int i=1;i<=m;++i){
		u=line[i].u,v=line[i].v;
		a[v][u]=(a[v][u]-d[u])%mod;
		if(a[v][u]<0) a[v][u]+=mod;
		if(line[i].o==0) continue;
		
		a[n+v][u]=(a[n+v][u]-d[u])%mod;
		if(a[n+v][u]<0) a[n+v][u]+=mod;
		a[n+v][n+u]=(a[n+v][n+u]-d[u])%mod;
		if(a[n+v][n+u]<0) a[n+v][n+u]+=mod;
		
		a[(n<<1)+v][u]=(a[(n<<1)+v][u]-d[u])%mod;
		if(a[(n<<1)+v][u]<0) a[(n<<1)+v][u]+=mod;
		a[(n<<1)+v][n+u]=(a[(n<<1)+v][n+u]-(d[u]<<1))%mod;
		if(a[(n<<1)+v][n+u]<0) a[(n<<1)+v][n+u]+=mod;
		a[(n<<1)+v][(n<<1)+u]=(a[(n<<1)+v][(n<<1)+u]-d[u])%mod;
		if(a[(n<<1)+v][(n<<1)+u]<0) a[(n<<1)+v][(n<<1)+u]+=mod;
	}
	solve(1,1,3*n,3*n+1);
	for(int i=1;i<=n;++i) f[i]=x[i];
	for(int i=n+1;i<=2*n;++i) g[i-n]=x[i];
	for(int i=2*n+1;i<=3*n;++i) h[i-2*n]=x[i];
	printf("%lld %lld",g[t],((h[t]-g[t]*g[t])%mod+mod)%mod);
//	for(int i=1;i<=n;++i) printf("%lld ",f[i]);printf("\n");
//	for(int i=1;i<=n;++i) printf("%lld ",g[i]);printf("\n");
//	for(int i=1;i<=n;++i) printf("%lld ",h[i]);printf("\n");
	
	return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 8ms

memory: 4480kb

input:

output:

0 0

result:

points 1.0

Test #2:

score: 4

Accepted

time: 10ms

memory: 4608kb

input:

90 7059 73 53
54 53 0
6 54 0
75 54 0
36 54 0
4 36 0
26 36 0
76 54 0
69 6 0
10 76 0
52 53 0
62 76 0
37 62 0
78 53 0
22 62 0
2 4 0
27 78 0
3 52 0
39 76 0
85 39 0
71 22 0
8 69 0
42 62 0
64 54 0
79 62 0
67 52 0
7 4 0
47 78 0
18 54 0
31 62 0
33 54 0
13 8 0
1 78 0
46 2 0
14 22 0
84 2 0
30 6 0
20 62 0
16 6...

output:

0 0

result:

points 1.0

Test #3:

score: 4

Accepted

time: 13ms

memory: 4608kb

input:

99 4727 84 99
33 99 0
5 33 0
65 99 0
51 33 0
4 33 0
89 65 0
62 89 0
68 33 0
84 4 0
59 4 0
35 59 0
53 35 0
15 68 0
10 62 0
27 15 0
80 5 0
50 65 0
63 99 0
49 89 0
57 80 0
1 50 0
56 10 0
8 89 0
31 68 0
85 80 0
39 50 0
72 15 0
55 4 0
76 57 0
96 76 0
66 62 0
13 63 0
3 76 0
11 4 0
20 80 0
79 11 0
61 63 0
...

output:

0 0

result:

points 1.0

Test #4:

score: 4

Accepted

time: 13ms

memory: 4736kb

input:

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

output:

0 0

result:

points 1.0

Test #5:

score: 4

Accepted

time: 9ms

memory: 4608kb

input:

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

output:

0 0

result:

points 1.0

Test #6:

score: 4

Accepted

time: 11ms

memory: 4608kb

input:

97 3283 84 80
53 80 0
42 53 0
36 42 0
41 36 0
17 41 0
48 17 0
25 48 0
19 25 0
73 19 0
72 73 0
30 72 0
22 30 0
33 22 0
64 33 0
90 64 0
66 90 0
69 66 0
68 69 0
7 68 0
83 7 0
40 83 0
39 40 0
26 39 0
70 26 0
44 70 0
61 44 0
81 61 0
47 81 0
92 47 0
65 92 0
11 65 0
29 11 0
54 29 0
16 54 0
85 16 0
31 85 0
...

output:

0 0

result:

points 1.0

Test #7:

score: 4

Accepted

time: 11ms

memory: 4608kb

input:

88 7044 78 88
70 88 0
51 88 0
63 88 0
18 70 0
28 51 0
47 70 0
53 47 0
66 18 0
10 51 0
48 66 0
73 47 0
87 73 0
49 63 0
16 28 0
76 51 0
17 73 0
81 70 0
12 28 0
43 73 0
8 70 0
31 88 0
69 53 0
20 81 0
30 12 0
65 70 0
80 31 0
59 81 0
29 31 0
78 76 0
6 80 0
25 63 0
40 49 0
26 70 0
2 17 0
50 48 0
56 17 0
5...

output:

0 0

result:

points 1.0

Subtask #2:

score: 0

Wrong Answer

Test #8:

score: 24

Accepted

time: 6ms

memory: 4352kb

input:

86 85 23 70
43 70 1
33 43 1
86 33 1
54 86 1
1 54 1
68 1 1
18 68 1
39 18 1
62 39 1
85 62 1
47 85 1
67 47 1
44 67 1
74 44 1
13 74 1
38 13 1
81 38 1
60 81 1
28 60 1
84 28 1
48 84 1
49 48 1
73 49 1
22 73 1
37 22 1
20 37 1
65 20 1
59 65 1
3 59 1
36 3 1
52 36 1
83 52 1
56 83 1
55 56 1
2 55 1
10 2 1
66 10 ...

output:

85 0

result:

points 1.0

Test #9:

score: 0

Wrong Answer

time: 24ms

memory: 4608kb

input:

92 5377 22 42
53 42 1
9 53 1
81 42 1
89 42 1
65 53 1
34 89 1
35 34 1
21 35 1
23 9 1
19 53 1
46 19 1
59 21 1
58 46 1
33 89 1
27 23 1
7 35 1
15 81 1
31 81 1
79 59 1
63 81 1
83 59 1
4 35 1
75 59 1
84 9 1
20 59 1
48 53 1
60 35 1
77 35 1
64 53 1
5 83 1
28 58 1
90 65 1
39 31 1
70 65 1
74 21 1
8 27 1
36 46...

output:

72335279 19351216

result:

points 0.0

Subtask #3:

score: 8

Accepted

Test #19:

score: 8

Accepted

time: 8ms

memory: 4480kb

input:

90 89 77 72
38 72 1
9 38 1
20 9 1
39 20 1
61 39 1
55 61 1
46 55 1
28 46 1
56 28 1
74 56 1
35 74 1
64 35 1
27 64 1
69 27 1
79 69 1
88 79 1
31 88 1
48 31 1
57 48 1
7 57 1
85 7 1
6 85 1
63 6 1
32 63 1
34 32 1
4 34 1
67 4 1
50 67 1
11 50 1
13 11 1
71 13 1
2 71 1
45 2 1
26 45 1
43 26 1
73 43 1
44 73 1
33...

output:

89 0

result:

points 1.0

Test #20:

score: 8

Accepted

time: 9ms

memory: 4352kb

input:

91 90 68 73
10 73 0
26 10 0
65 26 0
36 65 1
41 36 0
47 41 0
5 47 0
76 5 0
51 76 1
53 51 0
13 53 0
57 13 0
62 57 1
42 62 0
46 42 0
14 46 0
27 14 0
75 27 1
84 75 0
72 84 1
11 72 0
43 11 1
71 43 0
82 71 1
59 82 0
12 59 1
90 12 1
78 90 1
30 78 0
70 30 0
19 70 0
74 19 0
54 74 1
58 54 1
40 58 1
61 40 0
32...

output:

0 0

result:

points 1.0

Test #21:

score: 8

Accepted

time: 9ms

memory: 4608kb

input:

96 95 81 68
60 68 1
27 60 1
13 27 1
50 13 1
69 50 1
59 69 1
26 59 1
51 26 1
38 51 1
32 38 1
54 32 1
37 54 1
7 37 1
96 7 1
22 96 1
71 22 1
65 71 1
73 65 1
21 73 1
46 21 1
4 46 1
94 4 1
83 94 1
3 83 1
1 3 1
79 1 1
93 79 1
16 93 1
34 16 1
12 34 1
49 12 1
47 49 1
2 47 1
61 2 1
36 61 1
17 36 1
24 17 1
28...

output:

95 0

result:

points 1.0

Test #22:

score: 8

Accepted

time: 7ms

memory: 4480kb

input:

80 79 62 75
74 75 1
70 74 1
36 70 1
25 36 1
12 25 1
17 12 1
44 17 1
35 44 1
65 35 1
23 65 1
66 23 1
15 66 1
3 15 1
78 3 1
53 78 1
18 53 1
24 18 1
57 24 1
48 57 1
19 48 1
16 19 1
60 16 1
2 60 1
52 2 1
67 52 1
37 67 1
54 37 1
31 54 1
77 31 1
20 77 1
76 20 1
29 76 1
28 29 1
13 28 1
14 13 1
71 14 1
11 7...

output:

79 0

result:

points 1.0

Test #23:

score: 8

Accepted

time: 7ms

memory: 4480kb

input:

88 87 73 22
75 22 0
66 75 0
5 66 0
68 5 0
28 68 0
48 28 0
8 48 1
36 8 0
54 36 0
78 54 0
41 78 0
16 41 0
24 16 0
45 24 0
51 45 0
67 51 0
7 67 0
10 7 0
58 10 0
69 58 0
30 69 0
39 30 0
55 39 0
61 55 0
27 61 0
43 27 0
25 43 0
20 25 0
65 20 0
63 65 0
77 63 0
52 77 0
42 52 0
50 42 0
19 50 0
21 19 0
53 21 ...

output:

0 0

result:

points 1.0

Test #24:

score: 8

Accepted

time: 9ms

memory: 4352kb

input:

90 89 64 49
68 49 1
43 68 1
88 43 0
76 88 1
20 76 0
74 20 1
5 74 1
6 5 1
86 6 0
56 86 1
63 56 1
50 63 1
58 50 0
66 58 0
23 66 1
13 23 0
67 13 1
48 67 0
52 48 1
4 52 1
12 4 1
59 12 1
10 59 1
45 10 1
30 45 0
17 30 1
77 17 1
80 77 1
62 80 1
21 62 0
22 21 1
8 22 1
87 8 0
53 87 1
47 53 0
35 47 1
2 35 0
8...

output:

2 0

result:

points 1.0

Test #25:

score: 8

Accepted

time: 9ms

memory: 4608kb

input:

97 96 85 56
88 56 1
90 88 1
94 90 1
86 94 1
92 86 1
95 92 1
4 95 1
7 4 1
74 7 1
63 74 1
65 63 1
60 65 1
61 60 1
36 61 1
58 36 1
26 58 1
91 26 1
83 91 1
71 83 1
53 71 1
78 53 1
59 78 1
89 59 1
24 89 1
29 24 1
5 29 1
49 5 1
42 49 1
96 42 1
11 96 1
15 11 1
8 15 1
19 8 1
72 19 1
20 72 1
87 20 1
33 87 1
...

output:

96 0

result:

points 1.0

Subtask #4:

score: 20

Accepted

Test #26:

score: 20

Accepted

time: 9ms

memory: 4480kb

input:

81 6493 65 20
79 20 0
15 79 0
2 20 0
12 15 0
48 15 0
77 2 0
73 15 0
74 2 0
68 79 0
54 73 0
66 54 0
69 74 0
36 12 0
25 77 0
24 48 0
53 68 0
43 15 0
58 12 0
50 73 0
16 24 0
27 68 0
65 69 0
38 24 0
11 15 1
51 68 0
32 77 0
30 50 0
3 25 0
72 12 0
8 79 0
64 24 0
17 54 0
70 66 0
31 68 0
60 17 0
21 16 0
63 ...

output:

59424302 861956125

result:

points 1.0

Test #27:

score: 20

Accepted

time: 8ms

memory: 4608kb

input:

94 285 32 41
76 41 0
34 41 0
27 34 0
62 34 1
43 41 0
94 41 1
89 62 0
24 34 0
63 27 1
10 63 0
50 89 1
73 24 0
78 94 1
66 34 1
22 78 1
26 41 0
59 94 0
79 27 0
32 34 0
54 50 0
44 78 0
36 26 1
40 27 0
46 36 0
57 43 0
65 62 0
68 32 1
64 73 0
70 44 1
42 66 0
7 63 1
12 79 0
91 24 1
52 44 0
81 34 0
15 81 0
...

output:

0 0

result:

points 1.0

Test #28:

score: 20

Accepted

time: 12ms

memory: 4480kb

input:

82 3491 20 30
12 30 1
26 30 1
46 26 1
52 30 1
58 30 1
5 30 1
78 52 1
40 78 1
36 26 1
67 36 1
38 12 1
16 12 1
71 52 1
9 46 1
66 26 1
17 38 1
3 40 1
20 66 1
79 38 1
10 16 1
50 3 1
1 38 1
21 50 1
24 30 1
15 78 1
49 12 1
2 66 1
19 2 1
11 19 1
29 11 1
32 5 1
8 79 1
33 79 1
25 24 1
64 26 1
39 2 1
42 1 1
2...

output:

529988969 694645940

result:

points 1.0

Test #29:

score: 20

Accepted

time: 19ms

memory: 4480kb

input:

100 7227 94 11
88 11 0
46 88 0
72 88 0
37 88 0
47 37 1
59 37 0
23 47 0
36 11 0
93 47 0
22 11 0
84 59 0
12 59 1
10 11 0
5 47 1
70 88 1
96 22 1
42 23 0
8 11 1
17 88 0
77 23 1
86 46 1
55 59 0
62 93 0
58 93 0
38 10 0
68 17 1
73 36 0
48 55 0
40 5 0
94 86 0
100 58 1
65 94 0
25 55 1
43 11 1
15 86 0
89 55 1...

output:

78362322 459300466

result:

points 1.0

Test #30:

score: 20

Accepted

time: 19ms

memory: 4608kb

input:

98 5960 25 50
35 50 0
49 50 0
25 35 0
8 49 1
26 49 0
85 8 1
54 49 0
63 25 0
71 49 1
98 49 0
94 85 1
45 35 0
93 35 1
41 85 1
34 85 0
44 98 0
95 8 0
79 44 0
91 93 0
97 94 0
11 8 1
72 93 1
19 44 1
61 50 1
15 35 0
21 63 0
92 25 0
37 91 1
32 50 1
90 35 1
66 21 1
42 98 0
64 19 0
60 15 1
22 45 0
48 61 1
30...

output:

598946612 279508419

result:

points 1.0

Test #31:

score: 20

Accepted

time: 13ms

memory: 4480kb

input:

86 2583 14 75
36 75 0
35 75 0
4 36 0
27 75 1
12 4 0
51 12 0
60 75 1
59 36 0
41 4 1
55 12 1
49 12 0
66 12 0
65 75 0
21 66 1
29 21 0
2 36 0
79 29 0
54 66 1
18 49 0
84 21 1
16 60 0
61 16 0
53 49 1
42 18 1
38 12 1
34 12 1
11 49 0
62 51 0
48 84 1
63 66 1
72 61 0
70 35 0
6 54 1
86 38 0
69 86 0
44 69 0
52 ...

output:

618103890 50503659

result:

points 1.0

Test #32:

score: 20

Accepted

time: 15ms

memory: 4608kb

input:

89 7849 35 14
51 14 1
67 51 0
68 14 1
30 67 0
88 30 0
27 68 1
23 88 1
75 88 0
20 23 0
66 51 1
76 30 0
1 68 1
73 68 1
6 73 1
55 68 1
44 73 0
45 44 1
82 1 0
56 27 1
7 6 1
32 73 1
11 1 1
22 76 0
18 44 0
71 7 0
26 14 0
21 82 0
85 26 1
69 88 1
10 56 1
28 88 1
87 32 1
19 71 1
9 20 0
36 68 0
2 85 1
65 56 1...

output:

545871830 527934608

result:

points 1.0

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted