QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#562223	#8947. 白兔迷宫	Kevin5307^#	56	7ms	4248kb	C++23	2.3kb	2024-09-13 15:52:10	2024-09-13 15:52:10

Judging History

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

[2024-09-13 15:52:10]
评测

测评结果：56
用时：7ms
内存：4248kb

查看

[2024-09-13 15:52:10]
提交

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);
	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=ksm(deg[u[i]],mod-2);
			M2[u[i]][v[i]]=(M2[u[i]][v[i]]-p+mod)%mod;
		}
	M2[t][n]=1;
	vector<ll> g=EquationSolver::solve(M2);
	ll ans=0;
	for(int i=1;i<=m;i++)
		if(u[i]!=t&&c[i])
			ans=(ans+f[u[i]]*ksm(deg[u[i]],mod-2)%mod*g[v[i]])%mod;
	cout<<ans<<" 0"<<endl;
	return 0;
}

源文件, 语言: C++23

詳細信息

Subtask #1:

score: 4

Accepted

Test #1:

score: 4

Accepted

time: 3ms

memory: 3872kb

input:

output:

0 0

result:

points 1.0

Test #2:

score: 4

Accepted

time: 5ms

memory: 3892kb

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

memory: 3904kb

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

memory: 3980kb

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

memory: 3868kb

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

memory: 3884kb

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

memory: 3912kb

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

Acceptable Answer

Test #8:

score: 24

Accepted

time: 0ms

memory: 3788kb

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

memory: 3936kb

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

memory: 3852kb

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

memory: 3904kb

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

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

memory: 3900kb

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

memory: 4128kb

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

memory: 4152kb

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

memory: 3820kb

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

memory: 3876kb

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

memory: 4068kb

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

Accepted

Test #19:

score: 8

Accepted

time: 3ms

memory: 3868kb

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

memory: 3908kb

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

memory: 3828kb

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: 3764kb

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

memory: 3688kb

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

memory: 3864kb

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

memory: 4132kb

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

Acceptable Answer

Test #26:

score: 10

Acceptable Answer

time: 4ms

memory: 3800kb

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 0

result:

points 0.5

Test #27:

score: 20

Accepted

time: 4ms

memory: 3820kb

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

Acceptable Answer

time: 0ms

memory: 3848kb

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 0

result:

points 0.5

Test #29:

score: 10

Acceptable Answer

time: 6ms

memory: 4008kb

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 0

result:

points 0.5

Test #30:

score: 10

Acceptable Answer

time: 6ms

memory: 3976kb

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 0

result:

points 0.5

Test #31:

score: 10

Acceptable Answer

time: 4ms

memory: 4124kb

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 0

result:

points 0.5

Test #32:

score: 10

Acceptable Answer

time: 3ms

memory: 3900kb

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 0

result:

points 0.5

Subtask #5:

score: 22

Acceptable Answer

Dependency #1:

100%

Accepted

Dependency #2:

50%

Acceptable Answer

Dependency #3:

100%

Accepted

Dependency #4:

50%

Acceptable Answer

Test #33:

score: 44

Accepted

time: 3ms

memory: 3860kb

input:

90 89 90 46
7 46 0
75 7 1
77 75 0
14 77 0
1 14 1
25 1 1
64 25 0
40 64 1
49 40 1
8 49 0
2 8 1
56 2 0
66 56 0
54 66 0
83 54 0
47 83 1
21 47 0
65 21 0
79 65 0
16 79 1
87 16 0
88 87 0
39 88 1
11 39 1
78 11 0
52 78 0
61 52 0
44 61 0
6 44 1
18 6 1
42 18 0
63 42 0
23 63 0
24 23 0
86 24 0
85 86 0
37 85 0
31...

output:

0 0

result:

points 1.0

Test #34:

score: 22

Acceptable Answer

time: 3ms

memory: 3844kb

input:

81 579 78 80
79 80 1
60 79 1
45 60 1
8 45 1
11 8 1
70 11 1
18 70 1
34 18 1
5 34 1
77 5 1
55 77 1
69 55 1
68 69 1
25 68 1
6 25 1
30 6 1
47 30 1
59 47 1
44 59 1
12 44 1
22 12 1
81 22 1
48 81 1
28 48 1
51 28 1
35 51 1
10 35 1
65 10 1
40 65 1
3 40 1
74 3 1
14 74 1
39 14 1
43 39 1
64 43 1
54 64 1
42 54 1...

output:

132933873 0

result:

points 0.5

Test #35:

score: 44

Accepted

time: 4ms

memory: 3844kb

input:

94 1708 18 57
26 57 0
68 57 0
90 57 0
36 26 0
60 90 0
50 68 0
11 36 0
78 68 0
31 68 0
94 31 0
41 68 0
82 60 0
12 11 0
24 31 0
63 90 0
59 41 0
84 82 0
47 50 0
93 68 0
92 60 0
53 57 0
30 41 0
86 50 0
66 82 0
42 82 0
10 60 0
35 60 0
80 63 0
3 53 0
77 86 0
2 36 0
83 80 0
88 26 0
64 84 0
18 3 0
19 86 0
1...

output:

0 0

result:

points 1.0

Test #36:

score: 22

Acceptable Answer

time: 6ms

memory: 3932kb

input:

95 8076 24 13
69 13 0
73 13 1
37 73 0
4 37 0
14 13 0
78 73 0
57 69 1
71 78 0
36 4 0
12 69 0
93 57 0
29 78 0
81 14 0
60 78 0
56 57 0
55 78 0
92 56 0
77 81 0
66 73 0
54 60 0
64 37 1
94 73 0
49 55 0
59 13 0
80 66 0
75 56 0
31 49 0
45 13 1
22 55 1
48 92 0
38 57 0
10 92 0
41 54 0
6 4 0
18 81 0
33 55 0
91...

output:

121571635 0

result:

points 0.5

Test #37:

score: 22

Acceptable Answer

time: 7ms

memory: 4248kb

input:

99 9037 97 22
3 22 1
53 3 0
29 22 0
32 29 0
17 53 1
28 3 0
91 22 0
9 17 1
93 91 0
46 28 1
25 32 1
75 53 1
68 75 0
36 46 1
16 29 1
40 28 1
82 40 1
71 53 0
66 29 0
70 28 1
12 70 1
23 22 1
67 91 0
99 9 1
35 17 0
55 32 1
20 91 0
61 66 1
57 32 0
5 17 1
1 91 1
2 5 1
43 66 0
30 17 1
96 71 0
74 55 1
49 30 1...

output:

218327914 0

result:

points 0.5

Test #38:

score: 22

Acceptable Answer

time: 2ms

memory: 4112kb

input:

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

output:

171235504 0

result:

points 0.5

Test #39:

score: 22

Acceptable Answer

time: 4ms

memory: 4136kb

input:

80 6400 3 6
1 1 0
1 2 0
1 3 1
1 4 1
1 5 1
1 6 0
1 7 1
1 8 0
1 9 1
1 10 0
1 11 0
1 12 0
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 0
1 19 0
1 20 0
1 21 1
1 22 0
1 23 1
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 1
1 34 1
1 35 0
1 36 0
1 37 0
1 38 1
1 39 0
1 40 0
1 41 0
1 42 1
1 4...

output:

635770527 0

result:

points 0.5

Test #40:

score: 44

Accepted

time: 4ms

memory: 3920kb

input:

95 2230 8 74
62 74 0
35 62 0
76 35 0
28 76 0
47 74 0
27 76 0
59 76 0
84 35 0
14 28 0
83 35 0
10 76 0
17 10 0
2 47 0
90 17 0
45 28 0
11 2 0
70 2 0
86 59 0
67 35 0
21 11 0
68 17 0
13 28 0
95 21 0
71 14 0
92 11 0
82 10 0
79 84 0
89 62 0
46 13 0
61 17 0
63 82 0
57 17 0
51 89 0
32 74 0
87 71 0
56 14 0
91...

output:

0 0

result:

points 1.0

Test #41:

score: 22

Acceptable Answer

time: 7ms

memory: 3936kb

input:

100 6931 13 78
33 78 1
59 33 1
37 59 1
11 37 1
52 11 1
66 52 1
71 66 1
73 71 1
34 73 1
1 34 1
100 1 1
19 100 1
75 19 1
6 75 1
32 6 1
10 32 1
16 10 1
17 16 1
62 17 1
15 62 1
27 15 1
4 27 1
74 4 1
91 74 1
84 91 1
3 84 1
21 3 1
82 21 1
53 82 1
22 53 1
54 22 1
24 54 1
57 24 1
41 57 1
94 41 1
7 94 1
42 7...

output:

937347556 0

result:

points 0.5

Test #42:

score: 22

Acceptable Answer

time: 5ms

memory: 3828kb

input:

82 5095 20 73
54 73 1
78 54 1
49 54 1
79 78 1
22 49 0
7 73 1
60 79 1
50 79 1
19 49 1
62 7 1
71 54 1
31 22 1
4 7 1
69 49 1
40 49 1
36 78 1
72 73 1
34 36 1
21 36 0
6 40 1
8 6 1
56 36 1
32 6 1
9 54 1
58 19 1
16 58 1
25 56 1
67 25 1
48 50 1
77 56 1
10 40 1
55 9 1
15 21 1
11 9 1
27 69 1
75 55 1
74 11 1
8...

output:

145532970 0

result:

points 0.5

Test #43:

score: 22

Acceptable Answer

time: 4ms

memory: 4096kb

input:

90 2274 28 69
57 69 1
90 57 1
84 90 1
53 84 1
24 53 1
83 24 1
45 83 1
60 45 1
51 60 1
25 51 1
82 25 1
61 82 1
2 61 1
58 2 1
71 58 1
64 71 1
56 64 1
11 56 1
47 11 1
21 47 1
22 21 1
86 22 1
27 86 1
87 27 1
23 87 1
70 23 1
4 70 1
44 4 1
80 44 1
85 80 1
55 85 1
7 55 1
89 7 1
39 89 1
35 39 1
46 35 1
48 4...

output:

159667062 0

result:

points 0.5