QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#5891	#561. 税收	Qingyu	100 ✓	222ms	4344kb	C++17	1.9kb	2021-01-27 14:26:39	2021-12-19 07:07:08

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2021-12-19 07:07:08]
Judged

Verdict: 100
Time: 222ms
Memory: 4344kb

Show

[2021-01-27 14:26:39]
Submitted

answer

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
const int N = 205, M = 20005 << 1;
 
int n, m, p, s, t;
 
int top, head[N], to[M], nxt[M], c[M], l[M];
 
void addedge(int u, int v, int cap, int len) {
	to[top] = v, nxt[top] = head[u], c[top] = cap, l[top] = len, head[u] = top++;
}
 
vector<pair<int, int> > paths;
 
int dis[N], fa[N];
 
bool inque[N];
 
const int INF = 1000000000;
 
bool go(int source, int target) {
	for (int i = 0; i < n; ++i) {
		dis[i] = INF;
	}
	dis[source] = 0;
	inque[source] = true;
	queue<int> q;
	q.push(source);
	while (q.size()) {
		int u = q.front();
		inque[u] = false;
		q.pop();
		for (int i = head[u]; ~i; i = nxt[i]) {
			if (c[i]) {
				int v = to[i], nd = dis[u] + l[i];
				if (dis[v] > nd) {
					dis[v] = nd;
					fa[v] = i;
					if (!inque[v]) {
						inque[v] = true;
						q.push(v);
					}
				}
			}
		}
	}
	if (dis[target] == INF) {
		return false;
	}
	int f = INF;
	int u = target;
	while (u != source) {
		int e = fa[u];
		f = min(f, c[e]);
		u = to[e ^ 1];
	}
	paths.push_back(make_pair(f, dis[target]));
	u = target;
	while (u != source) {
		int e = fa[u];
		c[e] -= f, c[e ^ 1] += f;
		u = to[e ^ 1];
	}
	return true;
}
 
int main() { 
	scanf("%d%d%d%d%d", &n, &m, &p, &s, &t);
	--s, --t;
	top = 0;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; ++i) {
		int u, v, d, c;
		scanf("%d%d%d%d", &u, &v, &d, &c);
		--u, --v;
		addedge(u, v, c, d);
		addedge(v, u, 0, -d);
	}
	while (go(s, t)) {
		continue;
	}
	int csum = 0, fsum = 0;
	for (int i = 0; i < (int)paths.size(); ++i) {
		csum += paths[i].first * paths[i].second;
		fsum += paths[i].first;
		double ans = (double)(p + csum) / fsum;
		if (i + 1 == paths.size() || ans < paths[i + 1].second) {
			printf("%.4f\n", ans);
			return 0;
		}
	}
	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 0ms

memory: 3548kb

input:

100 99 10000 1 100
1 2 3 6
2 3 8 1
3 4 1 5
4 5 9 1
5 6 5 5
6 7 5 4
7 8 8 7
8 9 2 1
9 10 7 5
10 11 5 1
11 12 8 8
12 13 3 8
13 14 1 7
14 15 5 6
15 16 1 8
16 17 6 8
17 18 2 4
18 19 10 4
19 20 4 2
20 21 6 9
21 22 5 7
22 23 10 2
23 24 4 9
24 25 1 10
25 26 6 10
26 27 7 6
27 28 9 6
28 29 8 5
29 30 7 9
30 31 2 8
31 32 1 5
32 33 5 1
33 34 3 4
34 35 3 8
35 36 5 8
36 37 2 8
37 38 8 4
38 39 7 6
39 40 5 10
40 41 3 8
41 42 4 6
42 43 2 2
43 44 9 4
44 45 4 9
45 46 3 8
46 47 10 7
47 48 10 4
48 49 6 9
49 50 6 5
5...

output:

10497.0000

result:

ok found '10497.00000', expected '10497.00000', error '0.00000'

Test #2:

score: 10

Accepted

time: 2ms

memory: 3684kb

input:

30 100 10 1 30
1 2 1 1
2 3 5 1
3 4 4 1
4 5 2 1
5 6 10 1
6 7 1 1
7 30 2 1
23 26 4 1
11 5 5 1
26 25 6 1
26 21 5 1
11 6 6 1
27 12 4 1
14 27 1 1
17 26 2 1
21 29 4 1
27 29 2 1
14 19 8 1
29 21 9 1
28 2 6 1
18 12 5 1
27 12 3 1
14 13 10 1
4 6 9 1
23 11 10 1
4 22 2 1
23 24 1 1
23 1 5 1
5 10 6 1
17 27 5 1
8 9 7 1
14 24 4 1
18 28 8 1
14 12 6 1
5 20 10 1
13 20 8 1
1 14 3 1
4 3 3 1
10 28 5 1
30 2 6 1
24 8 5 1
8 13 7 1
6 2 8 1
19 7 6 1
1 19 3 1
25 19 9 1
15 7 10 1
14 21 2 1
29 8 3 1
29 10 10 1
13 9 7 1
1 13 5...

output:

21.0000

result:

ok found '21.00000', expected '21.00000', error '0.00000'

Test #3:

score: 10

Accepted

time: 2ms

memory: 3680kb

input:

50 150 60 1 50
1 2 5 1
2 3 8 1
3 50 2 1
11 24 8 1
3 50 8 1
28 24 7 1
14 3 7 1
37 23 7 1
13 15 7 1
42 27 8 1
50 3 2 1
29 31 5 1
4 23 9 1
33 20 8 1
38 13 3 1
43 3 10 1
4 17 5 1
17 1 5 1
10 35 8 1
45 17 9 1
31 10 5 1
26 25 2 1
31 4 2 1
9 37 4 1
44 50 6 1
49 5 2 1
3 28 4 1
27 23 6 1
32 29 4 1
45 27 8 1
13 31 2 1
48 30 8 1
4 42 7 1
48 50 6 1
41 18 4 1
8 43 10 1
50 35 7 1
19 40 7 1
8 34 8 1
26 29 10 1
2 7 7 1
41 6 4 1
22 3 3 1
45 38 3 1
13 23 6 1
40 22 5 1
30 8 2 1
21 22 7 1
18 26 2 1
11 29 5 1
20 19 ...

output:

37.2500

result:

ok found '37.25000', expected '37.25000', error '0.00000'

Test #4:

score: 10

Accepted

time: 0ms

memory: 3696kb

input:

50 200 72 1 50
1 2 4 1
2 3 4 1
3 4 5 1
4 5 10 1
5 6 3 1
6 7 8 1
7 8 9 1
8 9 9 1
9 10 7 1
10 50 7 1
17 16 10 1
26 45 8 1
21 41 6 1
2 12 9 1
32 40 9 1
28 7 8 1
2 13 7 1
1 13 1 1
11 50 10 1
33 20 10 1
14 17 3 1
43 25 4 1
31 47 5 1
48 27 4 1
42 12 6 1
41 23 2 1
27 36 2 1
5 19 4 1
13 38 6 1
50 41 5 1
6 47 10 1
45 33 1 1
4 30 7 1
2 15 5 1
36 41 6 1
35 46 10 1
35 4 3 1
29 28 4 1
26 12 2 1
1 12 7 1
24 44 4 1
15 24 1 1
44 43 1 1
44 16 2 1
43 25 9 1
3 6 2 1
3 2 6 1
32 50 3 1
30 18 7 1
42 37 3 1
4 38 3 1
3...

output:

33.4000

result:

ok found '33.40000', expected '33.40000', error '0.00000'

Test #5:

score: 10

Accepted

time: 2ms

memory: 3712kb

input:

100 400 300 1 100
1 2 3 5
2 3 10 3
3 4 2 7
4 5 2 1
5 6 8 4
6 7 10 3
7 8 5 9
8 9 10 8
9 10 1 8
10 11 10 5
11 12 6 10
12 13 10 5
13 14 9 2
14 15 10 2
15 16 4 7
16 17 8 6
17 18 5 1
18 19 9 2
19 20 4 4
20 100 3 6
3 7 8 10
18 20 8 8
70 93 1 8
51 87 10 3
47 41 7 6
54 13 4 7
19 37 1 8
50 72 9 3
61 82 5 7
80 55 5 8
55 43 1 2
30 76 5 4
5 81 1 2
52 77 6 5
24 76 10 6
8 89 3 6
34 19 9 9
20 3 10 10
95 17 6 3
50 40 6 10
70 60 10 8
6 59 7 4
48 23 10 10
88 16 4 4
38 26 10 7
33 5 9 7
8 71 1 9
32 68 4 6
17 47 2 7...

output:

29.6800

result:

ok found '29.68000', expected '29.68000', error '0.00000'

Test #6:

score: 10

Accepted

time: 43ms

memory: 4016kb

input:

200 10000 1000000 1 200
36 46 7 5
157 114 10 1
75 158 2 4
73 11 2 6
95 46 1 4
22 105 8 2
13 172 10 6
187 135 10 8
114 136 9 10
155 5 9 8
189 173 10 5
85 126 8 10
124 92 2 5
94 74 1 4
127 193 6 3
23 37 4 2
18 172 1 9
153 66 9 7
129 78 7 2
128 81 5 5
188 71 5 6
198 35 10 5
68 103 9 4
79 117 3 7
87 98 7 4
12 192 1 9
86 97 6 8
177 27 5 8
32 88 3 5
111 149 1 10
101 139 7 1
176 100 4 8
31 164 5 3
11 120 9 9
182 161 8 2
57 168 6 7
93 57 2 1
29 137 3 7
76 196 5 4
46 60 3 5
169 37 4 9
191 83 1 7
43 177 3...

output:

4707.4272

result:

ok found '4707.42720', expected '4707.42723', error '0.00000'

Test #7:

score: 10

Accepted

time: 24ms

memory: 3892kb

input:

100 5000 100 1 100
43 95 5 1
40 86 1 5
51 20 10 7
65 53 8 3
75 47 5 3
27 14 6 8
58 95 3 8
23 48 6 9
3 73 4 2
7 40 6 3
98 71 10 9
71 28 8 2
49 19 2 5
18 15 1 1
42 46 8 9
56 54 2 8
25 16 4 9
99 48 4 3
44 50 4 1
17 63 3 7
65 75 8 9
30 43 2 7
54 82 7 2
52 72 3 2
88 82 6 1
89 80 3 2
8 75 4 3
31 20 10 9
16 70 3 4
48 21 1 3
96 65 1 5
21 44 10 4
26 18 3 10
25 9 7 3
73 86 10 2
52 88 2 3
47 41 4 4
43 39 1 4
68 78 5 8
20 90 2 9
43 85 9 4
30 27 2 5
11 57 9 10
29 65 4 7
55 51 7 9
9 45 2 10
64 89 2 6
86 71 10...

output:

6.4143

result:

ok found '6.41430', expected '6.41429', error '0.00000'

Test #8:

score: 10

Accepted

time: 222ms

memory: 4344kb

input:

150 20000 2048 1 150
50 44 6 7
20 8 9 9
74 32 5 7
110 45 1 10
52 104 5 7
128 46 8 6
36 91 9 4
19 58 8 8
38 20 8 6
16 9 4 2
73 123 8 7
8 66 6 9
12 59 1 3
10 112 4 3
28 141 2 9
23 122 5 3
126 131 7 3
115 32 4 6
49 110 8 5
60 103 9 1
71 59 10 4
138 128 4 1
76 55 8 10
142 134 8 7
69 125 5 10
67 139 10 4
113 119 10 5
118 88 3 2
75 94 2 8
148 97 5 2
121 103 3 9
116 39 4 10
46 41 8 3
28 127 4 6
25 88 3 10
143 136 3 6
131 37 3 1
149 2 5 4
16 87 4 5
74 83 8 8
15 102 4 8
67 77 9 7
131 45 7 3
92 120 7 9
10...

output:

12.1576

result:

ok found '12.15760', expected '12.15762', error '0.00000'

Test #9:

score: 10

Accepted

time: 90ms

memory: 4176kb

input:

200 15000 1000 1 200
57 146 4 3
53 130 10 3
150 144 3 10
55 137 7 7
182 33 7 10
84 118 8 5
199 77 10 3
188 46 7 8
3 137 1 6
198 111 5 4
90 48 7 10
46 161 10 10
59 116 4 7
18 59 4 1
52 40 5 2
48 141 9 5
80 84 5 3
96 65 8 7
187 176 2 3
176 89 1 9
39 106 4 3
55 126 8 6
80 56 1 8
147 69 7 9
188 15 2 1
21 36 8 5
50 77 7 5
165 92 4 4
173 72 3 3
90 146 10 10
81 163 4 3
161 110 4 6
2 3 6 8
10 182 8 6
20 50 7 1
133 120 10 7
200 180 5 4
187 108 6 6
114 106 10 9
66 46 7 3
138 108 4 4
105 24 6 10
200 132 4 ...

output:

12.6869

result:

ok found '12.68690', expected '12.68687', error '0.00000'

Test #10:

score: 10

Accepted

time: 185ms

memory: 4268kb

input:

200 20000 1000000 1 200
64 195 5 6
183 2 1 7
26 6 8 10
100 179 10 4
62 162 9 10
187 40 8 7
112 10 8 2
4 134 3 8
115 4 4 9
177 60 9 6
10 73 3 6
131 106 1 8
53 73 10 8
79 3 4 2
129 189 8 5
123 7 3 4
34 90 3 10
77 198 9 5
22 142 9 8
192 25 10 4
107 200 8 2
125 121 5 4
84 154 4 9
5 151 6 4
104 105 6 9
122 86 6 6
187 188 4 5
59 149 8 6
118 200 4 1
32 145 2 1
141 120 2 7
156 31 7 2
8 165 1 10
92 187 9 3
68 162 1 5
76 104 7 8
169 170 7 4
122 67 7 1
9 25 3 3
155 6 6 1
14 167 4 7
143 71 10 10
119 66 8 8
...

output:

1882.9757

result:

ok found '1882.97570', expected '1882.97566', error '0.00000'