#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define SZ 262144
#define pii pair<int,int>
using namespace std;
int n, m;
vector<pii>G[201000];
long long S[201000], Z[201000], H[201000], T[201000];
int pv;
bool OK(long long K) {
int i;
long long s = 0;
for (i = 0; i < n; i++) {
H[i] = min(H[i], K);
T[i] = 0;
}
H[pv] = 0;
priority_queue<pii>PQ;
for (i = 1; i <= pv; i++) {
for (auto &t : G[i]) {
if(t.first > pv)PQ.push(t);
}
s += H[i - 1] - H[i];
while (s) {
if (PQ.empty())return false;
pii tp = PQ.top();
PQ.pop();
if (tp.second >= s) {
tp.second -= s;
T[tp.first] -= s;
PQ.push(tp);
s = 0;
}
else {
T[tp.first] -= tp.second;
s -= tp.second;
}
}
}
for (i = 1; i < n; i++) {
T[i] += T[i - 1];
if (T[i] + H[i] < 0)return false;
}
return true;
}
bool Pos(long long M) {
long long i, j;
long long bb = Z[pv] - M, ee = M / 2;
for (i = bb; i <= bb + 1; i++) {
for (j = 0; j < n; j++) {
H[j] = (i + M - Z[j]) / 2;
}
if (H[0] < i)continue;
if (OK(i))return true;
}
return false;
}
int main() {
int i;
//freopen("input.txt","r",stdin);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (a > b)swap(a, b);
G[a].push_back({ b,c });
S[a] += c;
S[b] -= c;
}
long long Mx = -1;
pv = -1;
for (i = 1; i < n; i++) {
S[i] += S[i - 1];
if (Mx < S[i]) {
Mx = S[i];
pv = i;
}
}
for (i = 1; i <= pv; i++)Z[i] = max(Z[i - 1], S[i]);
for (i = n - 1; i >= pv; i--)Z[i] = max(Z[i + 1], S[i]);
long long b = 0, e = Mx - 1, mid, r = Mx;
while (b <= e) {
mid = (b + e) >> 1;
if (Pos(mid)) {
r = mid;
e = mid - 1;
}
else b = mid + 1;
}
printf("%lld\n", r);
}
Compilation message
arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
arranging_tickets.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
5116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
5116 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5112 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
6 ms |
5112 KB |
Output is correct |
24 |
Correct |
6 ms |
5112 KB |
Output is correct |
25 |
Correct |
6 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5112 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
5116 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5112 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
6 ms |
5112 KB |
Output is correct |
24 |
Correct |
6 ms |
5112 KB |
Output is correct |
25 |
Correct |
6 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5112 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5240 KB |
Output is correct |
29 |
Correct |
12 ms |
5240 KB |
Output is correct |
30 |
Correct |
10 ms |
5252 KB |
Output is correct |
31 |
Correct |
12 ms |
5300 KB |
Output is correct |
32 |
Correct |
11 ms |
5240 KB |
Output is correct |
33 |
Correct |
10 ms |
5240 KB |
Output is correct |
34 |
Correct |
11 ms |
5240 KB |
Output is correct |
35 |
Correct |
10 ms |
5240 KB |
Output is correct |
36 |
Correct |
10 ms |
5240 KB |
Output is correct |
37 |
Correct |
9 ms |
5368 KB |
Output is correct |
38 |
Correct |
7 ms |
5216 KB |
Output is correct |
39 |
Correct |
8 ms |
5240 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
5116 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5112 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
6 ms |
5112 KB |
Output is correct |
24 |
Correct |
6 ms |
5112 KB |
Output is correct |
25 |
Correct |
6 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5112 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5240 KB |
Output is correct |
29 |
Correct |
12 ms |
5240 KB |
Output is correct |
30 |
Correct |
10 ms |
5252 KB |
Output is correct |
31 |
Correct |
12 ms |
5300 KB |
Output is correct |
32 |
Correct |
11 ms |
5240 KB |
Output is correct |
33 |
Correct |
10 ms |
5240 KB |
Output is correct |
34 |
Correct |
11 ms |
5240 KB |
Output is correct |
35 |
Correct |
10 ms |
5240 KB |
Output is correct |
36 |
Correct |
10 ms |
5240 KB |
Output is correct |
37 |
Correct |
9 ms |
5368 KB |
Output is correct |
38 |
Correct |
7 ms |
5216 KB |
Output is correct |
39 |
Correct |
8 ms |
5240 KB |
Output is correct |
40 |
Correct |
287 ms |
15876 KB |
Output is correct |
41 |
Correct |
310 ms |
16064 KB |
Output is correct |
42 |
Correct |
274 ms |
15600 KB |
Output is correct |
43 |
Correct |
367 ms |
15672 KB |
Output is correct |
44 |
Correct |
222 ms |
15880 KB |
Output is correct |
45 |
Correct |
378 ms |
15508 KB |
Output is correct |
46 |
Correct |
309 ms |
15556 KB |
Output is correct |
47 |
Correct |
339 ms |
15756 KB |
Output is correct |
48 |
Correct |
279 ms |
15384 KB |
Output is correct |
49 |
Correct |
183 ms |
13180 KB |
Output is correct |
50 |
Correct |
80 ms |
12720 KB |
Output is correct |
51 |
Correct |
177 ms |
12748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5112 KB |
Output is correct |
3 |
Correct |
6 ms |
5112 KB |
Output is correct |
4 |
Correct |
6 ms |
5112 KB |
Output is correct |
5 |
Correct |
6 ms |
5112 KB |
Output is correct |
6 |
Correct |
6 ms |
4984 KB |
Output is correct |
7 |
Correct |
6 ms |
4984 KB |
Output is correct |
8 |
Correct |
6 ms |
5112 KB |
Output is correct |
9 |
Correct |
6 ms |
5112 KB |
Output is correct |
10 |
Correct |
6 ms |
4984 KB |
Output is correct |
11 |
Correct |
6 ms |
4984 KB |
Output is correct |
12 |
Correct |
6 ms |
5112 KB |
Output is correct |
13 |
Correct |
6 ms |
5112 KB |
Output is correct |
14 |
Correct |
6 ms |
4984 KB |
Output is correct |
15 |
Correct |
6 ms |
5116 KB |
Output is correct |
16 |
Correct |
6 ms |
5112 KB |
Output is correct |
17 |
Correct |
6 ms |
5112 KB |
Output is correct |
18 |
Correct |
6 ms |
5112 KB |
Output is correct |
19 |
Correct |
6 ms |
5112 KB |
Output is correct |
20 |
Correct |
6 ms |
5112 KB |
Output is correct |
21 |
Correct |
6 ms |
5116 KB |
Output is correct |
22 |
Correct |
6 ms |
5112 KB |
Output is correct |
23 |
Correct |
6 ms |
5112 KB |
Output is correct |
24 |
Correct |
6 ms |
5112 KB |
Output is correct |
25 |
Correct |
6 ms |
5112 KB |
Output is correct |
26 |
Correct |
6 ms |
5112 KB |
Output is correct |
27 |
Correct |
6 ms |
5112 KB |
Output is correct |
28 |
Correct |
12 ms |
5240 KB |
Output is correct |
29 |
Correct |
12 ms |
5240 KB |
Output is correct |
30 |
Correct |
10 ms |
5252 KB |
Output is correct |
31 |
Correct |
12 ms |
5300 KB |
Output is correct |
32 |
Correct |
11 ms |
5240 KB |
Output is correct |
33 |
Correct |
10 ms |
5240 KB |
Output is correct |
34 |
Correct |
11 ms |
5240 KB |
Output is correct |
35 |
Correct |
10 ms |
5240 KB |
Output is correct |
36 |
Correct |
10 ms |
5240 KB |
Output is correct |
37 |
Correct |
9 ms |
5368 KB |
Output is correct |
38 |
Correct |
7 ms |
5216 KB |
Output is correct |
39 |
Correct |
8 ms |
5240 KB |
Output is correct |
40 |
Correct |
287 ms |
15876 KB |
Output is correct |
41 |
Correct |
310 ms |
16064 KB |
Output is correct |
42 |
Correct |
274 ms |
15600 KB |
Output is correct |
43 |
Correct |
367 ms |
15672 KB |
Output is correct |
44 |
Correct |
222 ms |
15880 KB |
Output is correct |
45 |
Correct |
378 ms |
15508 KB |
Output is correct |
46 |
Correct |
309 ms |
15556 KB |
Output is correct |
47 |
Correct |
339 ms |
15756 KB |
Output is correct |
48 |
Correct |
279 ms |
15384 KB |
Output is correct |
49 |
Correct |
183 ms |
13180 KB |
Output is correct |
50 |
Correct |
80 ms |
12720 KB |
Output is correct |
51 |
Correct |
177 ms |
12748 KB |
Output is correct |
52 |
Correct |
677 ms |
16952 KB |
Output is correct |
53 |
Correct |
839 ms |
16620 KB |
Output is correct |
54 |
Correct |
1217 ms |
16948 KB |
Output is correct |
55 |
Correct |
537 ms |
16672 KB |
Output is correct |
56 |
Correct |
920 ms |
16428 KB |
Output is correct |
57 |
Correct |
1222 ms |
16460 KB |
Output is correct |
58 |
Correct |
845 ms |
16584 KB |
Output is correct |
59 |
Correct |
616 ms |
13928 KB |
Output is correct |