QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#562210	#8947. 白兔迷宫	Kevin5307^#	18	3ms	4116kb	C++23	2.3kb	2024-09-13 15:45:25	2024-09-13 15:45:25

Judging History

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

[2024-09-13 15:45:25]
评测

测评结果：18
用时：3ms
内存：4116kb

查看

[2024-09-13 15:45:25]
提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
namespace EquationSolver
{
	vector<ll> solve(vector<vector<ll>> M)
	{
		int n=sz(M);
		for(int i=0;i<n;i++)
			assert(sz(M[i])==n+1);
		for(int i=0;i<n;i++)
		{
			if(!M[i][i])
				for(int j=i+1;j<n;j++)
					if(M[j][i])
					{
						swap(M[i],M[j]);
						break;
					}
			assert(M[i][i]);
			ll inv=ksm(M[i][i],mod-2);
			for(auto &x:M[i])
				x=x*inv%mod;
			for(int j=0;j<n;j++)
				if(i!=j)
				{
					ll v=M[j][i];
					for(int k=0;k<=n;k++)
						M[j][k]=(M[j][k]+mod-M[i][k]*v%mod)%mod;
				}
		}
		vector<ll> ret;
		for(int i=0;i<n;i++)
			ret.pb(M[i][n]);
		return ret;
	}
}
int n,m,s,t;
int u[10010],v[10010],c[10010];
int deg[10010];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s>>t;
	s--;
	t--;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i]>>c[i];
		u[i]--;
		v[i]--;
		deg[u[i]]++;
	}
	vector<vector<ll>> M1(n,vector<ll>(n+1));
	for(int i=0;i<n;i++)
		M1[i][i]=1;
	for(int i=1;i<=m;i++)
		if(u[i]!=t)
			M1[v[i]][u[i]]=(M1[v[i]][u[i]]-ksm(deg[u[i]],mod-2)+mod)%mod;
	M1[s][n]=1;
	vector<ll> f=EquationSolver::solve(M1);
	if(!c[1])
		die("0");
	cout<<accumulate(ALL(f),-1ll)%mod<<" 0"<<endl;
	return 0;
	vector<vector<ll>> M2(n,vector<ll>(n+1));
	for(int i=0;i<n;i++)
		M2[i][i]=1;
	for(int i=1;i<=m;i++)
		if(u[i]!=t&&c[i])
		{
			ll p=f[u[i]]*ksm(deg[u[i]],mod-2)%mod;
			M2[v[i]][u[i]]=(M2[v[i]][u[i]]-p+mod)%mod;
			M2[v[i]][n]=(M2[v[i]][n]+p)%mod;
		}
	vector<ll> g=EquationSolver::solve(M2);
	cout<<g[t]<<" 0"<<endl;
	return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 2

Acceptable Answer

Test #1:

score: 2

Acceptable Answer

time: 2ms

memory: 3932kb

input:

output:

result:

points 0.5

Test #2:

score: 2

Acceptable Answer

time: 3ms

memory: 4072kb

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:

result:

points 0.5

Test #3:

score: 2

Acceptable Answer

time: 3ms

memory: 3848kb

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:

result:

points 0.5

Test #4:

score: 2

Acceptable Answer

time: 2ms

memory: 4116kb

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:

result:

points 0.5

Test #5:

score: 2

Acceptable Answer

time: 0ms

memory: 4064kb

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:

result:

points 0.5

Test #6:

score: 2

Acceptable Answer

time: 3ms

memory: 3760kb

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:

result:

points 0.5

Test #7:

score: 2

Acceptable Answer

time: 3ms

memory: 3780kb

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:

result:

points 0.5

Subtask #2:

score: 12

Acceptable Answer

Test #8:

score: 24

Accepted

time: 2ms

memory: 3664kb

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: 12

Acceptable Answer

time: 0ms

memory: 3992kb

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:

791755969 0

result:

points 0.5

Test #10:

score: 12

Acceptable Answer

time: 2ms

memory: 4004kb

input:

89 3236 53 39
6 39 1
63 39 1
33 6 1
54 39 1
89 39 1
78 89 1
52 33 1
75 52 1
15 63 1
42 33 1
49 75 1
5 89 1
55 52 1
17 5 1
70 49 1
16 89 1
85 39 1
14 85 1
66 89 1
68 75 1
20 63 1
76 63 1
81 85 1
27 70 1
2 89 1
40 42 1
60 2 1
57 16 1
46 54 1
59 81 1
11 17 1
8 17 1
82 2 1
71 52 1
3 5 1
44 3 1
80 14 1
7...

output:

241617573 0

result:

points 0.5

Test #11:

score: 12

Acceptable Answer

time: 3ms

memory: 3788kb

input:

98 4882 40 87
85 87 1
53 85 1
73 87 1
93 53 1
74 53 1
9 73 1
50 73 1
65 9 1
38 9 1
67 87 1
37 9 1
64 74 1
47 67 1
26 85 1
68 9 1
31 87 1
13 37 1
44 73 1
10 93 1
91 87 1
76 13 1
41 93 1
55 87 1
24 87 1
88 68 1
25 38 1
34 93 1
2 64 1
29 93 1
69 37 1
98 31 1
20 69 1
39 13 1
72 55 1
83 37 1
77 64 1
90 8...

output:

616152076 0

result:

points 0.5

Test #12:

score: 12

Acceptable Answer

time: 2ms

memory: 3796kb

input:

89 2544 67 60
9 60 1
69 9 1
74 9 1
61 69 1
72 61 1
13 9 1
45 13 1
14 61 1
31 9 1
16 60 1
84 60 1
80 69 1
83 45 1
40 69 1
25 9 1
47 61 1
5 74 1
8 31 1
10 40 1
23 5 1
70 10 1
51 69 1
35 60 1
81 13 1
34 61 1
36 14 1
38 31 1
58 83 1
49 45 1
75 38 1
15 38 1
21 84 1
65 70 1
66 31 1
20 10 1
54 81 1
53 81 1...

output:

797093300 0

result:

points 0.5

Test #13:

score: 12

Acceptable Answer

time: 3ms

memory: 3896kb

input:

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

output:

89 0

result:

points 0.5

Test #14:

score: 12

Acceptable Answer

time: 0ms

memory: 3864kb

input:

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

output:

90 0

result:

points 0.5

Test #15:

score: 12

Acceptable Answer

time: 3ms

memory: 3836kb

input:

91 4288 63 78
65 78 1
74 78 1
56 74 1
16 74 1
91 65 1
30 56 1
3 65 1
40 91 1
29 65 1
48 40 1
88 91 1
57 29 1
19 40 1
21 78 1
28 56 1
13 30 1
75 65 1
11 30 1
84 74 1
7 3 1
12 13 1
85 16 1
86 85 1
67 12 1
20 57 1
17 67 1
69 20 1
24 28 1
47 17 1
27 11 1
15 69 1
41 74 1
87 16 1
89 13 1
53 28 1
76 91 1
8...

output:

114706894 0

result:

points 0.5

Test #16:

score: 12

Acceptable Answer

time: 2ms

memory: 3732kb

input:

86 3062 25 41
36 41 1
22 36 1
73 22 1
72 73 1
26 72 1
42 26 1
54 42 1
6 54 1
78 6 1
82 78 1
49 82 1
17 49 1
30 17 1
51 30 1
23 51 1
37 23 1
18 37 1
55 18 1
63 55 1
27 63 1
12 27 1
34 12 1
20 34 1
8 20 1
44 8 1
38 44 1
71 38 1
2 71 1
74 2 1
4 74 1
45 4 1
79 45 1
3 79 1
35 3 1
62 35 1
67 62 1
32 67 1
...

output:

422980980 0

result:

points 0.5

Test #17:

score: 12

Acceptable Answer

time: 2ms

memory: 3784kb

input:

83 2712 11 64
31 64 1
30 31 1
36 64 1
80 36 1
81 31 1
33 64 1
24 30 1
74 81 1
67 24 1
38 74 1
58 81 1
41 38 1
66 36 1
63 38 1
19 67 1
72 66 1
28 72 1
43 58 1
47 66 1
14 47 1
12 28 1
55 12 1
62 30 1
21 30 1
52 12 1
11 41 1
32 24 1
37 30 1
18 11 1
5 38 1
44 43 1
20 11 1
53 66 1
40 20 1
56 64 1
4 74 1
...

output:

817061307 0

result:

points 0.5

Test #18:

score: 12

Acceptable Answer

time: 3ms

memory: 3804kb

input:

84 4693 16 71
1 71 1
51 1 1
34 51 1
49 34 1
27 49 1
21 27 1
39 21 1
78 39 1
20 78 1
9 20 1
40 9 1
73 40 1
84 73 1
68 84 1
3 68 1
2 3 1
12 2 1
53 12 1
15 53 1
38 15 1
7 38 1
29 7 1
13 29 1
45 13 1
31 45 1
41 31 1
54 41 1
69 54 1
36 69 1
4 36 1
25 4 1
57 25 1
83 57 1
46 83 1
52 46 1
61 52 1
55 61 1
5 ...

output:

833057197 0

result:

points 0.5

Subtask #3:

score: 4

Acceptable Answer

Test #19:

score: 8

Accepted

time: 2ms

memory: 3740kb

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: 4

Acceptable Answer

time: 2ms

memory: 3804kb

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:

result:

points 0.5

Test #21:

score: 8

Accepted

time: 2ms

memory: 3724kb

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: 2ms

memory: 3680kb

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: 4

Acceptable Answer

time: 2ms

memory: 3756kb

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:

result:

points 0.5

Test #24:

score: 4

Acceptable Answer

time: 2ms

memory: 3772kb

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:

89 0

result:

points 0.5

Test #25:

score: 8

Accepted

time: 2ms

memory: 3788kb

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: 0

Wrong Answer

Test #26:

score: 0

Wrong Answer

time: 3ms

memory: 3824kb

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:

result:

points 0.0

Subtask #5:

score: 0

Skipped

Dependency #1:

50%

Acceptable Answer

Dependency #2:

50%

Acceptable Answer

Dependency #3:

50%

Acceptable Answer