#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5;
typedef long long ll;
priority_queue< pair<int,int> > heap;
ll start[Nmax], finish[Nmax], add[Nmax], dp[Nmax], s[Nmax];
vector< pair<int,int> > v[Nmax];
int n, m, i, A, B;
struct Edge
{
int x, y, c;
};
vector< Edge > edges;
int mod(int x)
{
if(x <= 0) return x+n;
if(x>n) return x-n;
return x;
}
bool check_center(int where, ll L)
{
int i;
ll need = 0;
for(i=1; i<=n; ++i) v[i].clear();
for(i=1; i<=n; ++i) start[i] = 0, finish[i] = 0, add[i] = 0;
while(heap.size()) heap.pop();
for(auto e : edges)
{
int x, y;
x = mod(e.x - where + 1);
y = mod(e.y - where + 1);
if(x > y) swap(x, y);
v[x].push_back({y, e.c});
start[x] += e.c;
finish[y] += e.c;
}
dp[0] = L;
for(i=1; i<n; ++i)
{
for(auto it : v[i]) heap.push(it);
dp[i] = dp[i-1] + start[i] - finish[i] + add[i];
while(dp[i] > L)
{
assert(heap.size());
auto el = heap.top();
heap.pop();
if(dp[i] - 2 * el.second >= L)
{
dp[i] -= 2 * el.second;
add[el.first] += 2 * el.second;
need += el.second;
}
else
{
ll cat = (dp[i] - L + 1) / 2;
dp[i] -= 2 * cat;
add[el.first] += 2 * cat;
need += cat;
heap.push({el.first, el.second - cat});
}
}
if(need > L) return 0;
}
return (need <= L);
}
bool check(ll L)
{
return (check_center(A, L) || check_center(B, L));
}
int best_point(bool dir)
{
int i;
for(i=1; i<=n; ++i) s[i] = 0;
for(auto e : edges)
if(dir == 0)
{
s[e.x] += e.c;
s[e.y] -= e.c;
}
else
{
s[e.y] += e.c;
s[1] += e.c;
s[e.x] -= e.c;
}
for(i=1; i<=n; ++i) s[i] += s[i-1];
ll Max = 0;
for(i=1; i<=n; ++i) Max = max(Max, s[i]);
for(i=1; i<=n; ++i)
if(Max == s[i]) return mod(i+1);
}
int main()
{
// freopen("input", "r", stdin);
cin >> n >> m;
int i, x, y, C;
for(i=1; i<=m; ++i)
{
cin >> x >> y >> C;
if(x > y) swap(x, y);
edges.push_back({x, y, C});
}
A = best_point(0);
B = best_point(1);
ll st = 0, dr = m * (1e9), mid;
while(st <= dr)
{
mid = (st+dr) / 2;
if(check(mid)) dr = mid - 1;
else st = mid + 1;
}
cout << st << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5144 KB |
Output is correct |
4 |
Correct |
6 ms |
5192 KB |
Output is correct |
5 |
Correct |
6 ms |
5192 KB |
Output is correct |
6 |
Correct |
5 ms |
5192 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5276 KB |
Output is correct |
10 |
Correct |
6 ms |
5276 KB |
Output is correct |
11 |
Correct |
6 ms |
5276 KB |
Output is correct |
12 |
Correct |
5 ms |
5276 KB |
Output is correct |
13 |
Correct |
6 ms |
5276 KB |
Output is correct |
14 |
Correct |
5 ms |
5280 KB |
Output is correct |
15 |
Correct |
6 ms |
5280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5144 KB |
Output is correct |
4 |
Correct |
6 ms |
5192 KB |
Output is correct |
5 |
Correct |
6 ms |
5192 KB |
Output is correct |
6 |
Correct |
5 ms |
5192 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5276 KB |
Output is correct |
10 |
Correct |
6 ms |
5276 KB |
Output is correct |
11 |
Correct |
6 ms |
5276 KB |
Output is correct |
12 |
Correct |
5 ms |
5276 KB |
Output is correct |
13 |
Correct |
6 ms |
5276 KB |
Output is correct |
14 |
Correct |
5 ms |
5280 KB |
Output is correct |
15 |
Correct |
6 ms |
5280 KB |
Output is correct |
16 |
Correct |
6 ms |
5368 KB |
Output is correct |
17 |
Correct |
6 ms |
5368 KB |
Output is correct |
18 |
Correct |
6 ms |
5368 KB |
Output is correct |
19 |
Correct |
6 ms |
5476 KB |
Output is correct |
20 |
Correct |
7 ms |
5484 KB |
Output is correct |
21 |
Correct |
6 ms |
5484 KB |
Output is correct |
22 |
Correct |
7 ms |
5484 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
6 ms |
5484 KB |
Output is correct |
25 |
Correct |
6 ms |
5484 KB |
Output is correct |
26 |
Correct |
7 ms |
5484 KB |
Output is correct |
27 |
Correct |
6 ms |
5484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5144 KB |
Output is correct |
4 |
Correct |
6 ms |
5192 KB |
Output is correct |
5 |
Correct |
6 ms |
5192 KB |
Output is correct |
6 |
Correct |
5 ms |
5192 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5276 KB |
Output is correct |
10 |
Correct |
6 ms |
5276 KB |
Output is correct |
11 |
Correct |
6 ms |
5276 KB |
Output is correct |
12 |
Correct |
5 ms |
5276 KB |
Output is correct |
13 |
Correct |
6 ms |
5276 KB |
Output is correct |
14 |
Correct |
5 ms |
5280 KB |
Output is correct |
15 |
Correct |
6 ms |
5280 KB |
Output is correct |
16 |
Correct |
6 ms |
5368 KB |
Output is correct |
17 |
Correct |
6 ms |
5368 KB |
Output is correct |
18 |
Correct |
6 ms |
5368 KB |
Output is correct |
19 |
Correct |
6 ms |
5476 KB |
Output is correct |
20 |
Correct |
7 ms |
5484 KB |
Output is correct |
21 |
Correct |
6 ms |
5484 KB |
Output is correct |
22 |
Correct |
7 ms |
5484 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
6 ms |
5484 KB |
Output is correct |
25 |
Correct |
6 ms |
5484 KB |
Output is correct |
26 |
Correct |
7 ms |
5484 KB |
Output is correct |
27 |
Correct |
6 ms |
5484 KB |
Output is correct |
28 |
Correct |
28 ms |
5500 KB |
Output is correct |
29 |
Correct |
25 ms |
5500 KB |
Output is correct |
30 |
Correct |
26 ms |
5628 KB |
Output is correct |
31 |
Correct |
26 ms |
5664 KB |
Output is correct |
32 |
Correct |
26 ms |
5700 KB |
Output is correct |
33 |
Correct |
26 ms |
5732 KB |
Output is correct |
34 |
Correct |
27 ms |
5832 KB |
Output is correct |
35 |
Correct |
26 ms |
5832 KB |
Output is correct |
36 |
Correct |
28 ms |
5836 KB |
Output is correct |
37 |
Correct |
20 ms |
5868 KB |
Output is correct |
38 |
Correct |
20 ms |
5904 KB |
Output is correct |
39 |
Correct |
20 ms |
5940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5144 KB |
Output is correct |
4 |
Correct |
6 ms |
5192 KB |
Output is correct |
5 |
Correct |
6 ms |
5192 KB |
Output is correct |
6 |
Correct |
5 ms |
5192 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5276 KB |
Output is correct |
10 |
Correct |
6 ms |
5276 KB |
Output is correct |
11 |
Correct |
6 ms |
5276 KB |
Output is correct |
12 |
Correct |
5 ms |
5276 KB |
Output is correct |
13 |
Correct |
6 ms |
5276 KB |
Output is correct |
14 |
Correct |
5 ms |
5280 KB |
Output is correct |
15 |
Correct |
6 ms |
5280 KB |
Output is correct |
16 |
Correct |
6 ms |
5368 KB |
Output is correct |
17 |
Correct |
6 ms |
5368 KB |
Output is correct |
18 |
Correct |
6 ms |
5368 KB |
Output is correct |
19 |
Correct |
6 ms |
5476 KB |
Output is correct |
20 |
Correct |
7 ms |
5484 KB |
Output is correct |
21 |
Correct |
6 ms |
5484 KB |
Output is correct |
22 |
Correct |
7 ms |
5484 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
6 ms |
5484 KB |
Output is correct |
25 |
Correct |
6 ms |
5484 KB |
Output is correct |
26 |
Correct |
7 ms |
5484 KB |
Output is correct |
27 |
Correct |
6 ms |
5484 KB |
Output is correct |
28 |
Correct |
28 ms |
5500 KB |
Output is correct |
29 |
Correct |
25 ms |
5500 KB |
Output is correct |
30 |
Correct |
26 ms |
5628 KB |
Output is correct |
31 |
Correct |
26 ms |
5664 KB |
Output is correct |
32 |
Correct |
26 ms |
5700 KB |
Output is correct |
33 |
Correct |
26 ms |
5732 KB |
Output is correct |
34 |
Correct |
27 ms |
5832 KB |
Output is correct |
35 |
Correct |
26 ms |
5832 KB |
Output is correct |
36 |
Correct |
28 ms |
5836 KB |
Output is correct |
37 |
Correct |
20 ms |
5868 KB |
Output is correct |
38 |
Correct |
20 ms |
5904 KB |
Output is correct |
39 |
Correct |
20 ms |
5940 KB |
Output is correct |
40 |
Correct |
2204 ms |
19320 KB |
Output is correct |
41 |
Correct |
2112 ms |
19400 KB |
Output is correct |
42 |
Correct |
2151 ms |
19400 KB |
Output is correct |
43 |
Correct |
1928 ms |
19400 KB |
Output is correct |
44 |
Correct |
2029 ms |
19516 KB |
Output is correct |
45 |
Correct |
1867 ms |
19516 KB |
Output is correct |
46 |
Correct |
1902 ms |
19516 KB |
Output is correct |
47 |
Correct |
1476 ms |
19516 KB |
Output is correct |
48 |
Correct |
1716 ms |
19516 KB |
Output is correct |
49 |
Correct |
968 ms |
19516 KB |
Output is correct |
50 |
Correct |
1194 ms |
19516 KB |
Output is correct |
51 |
Correct |
988 ms |
19516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
5 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5144 KB |
Output is correct |
4 |
Correct |
6 ms |
5192 KB |
Output is correct |
5 |
Correct |
6 ms |
5192 KB |
Output is correct |
6 |
Correct |
5 ms |
5192 KB |
Output is correct |
7 |
Correct |
5 ms |
5248 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
6 ms |
5276 KB |
Output is correct |
10 |
Correct |
6 ms |
5276 KB |
Output is correct |
11 |
Correct |
6 ms |
5276 KB |
Output is correct |
12 |
Correct |
5 ms |
5276 KB |
Output is correct |
13 |
Correct |
6 ms |
5276 KB |
Output is correct |
14 |
Correct |
5 ms |
5280 KB |
Output is correct |
15 |
Correct |
6 ms |
5280 KB |
Output is correct |
16 |
Correct |
6 ms |
5368 KB |
Output is correct |
17 |
Correct |
6 ms |
5368 KB |
Output is correct |
18 |
Correct |
6 ms |
5368 KB |
Output is correct |
19 |
Correct |
6 ms |
5476 KB |
Output is correct |
20 |
Correct |
7 ms |
5484 KB |
Output is correct |
21 |
Correct |
6 ms |
5484 KB |
Output is correct |
22 |
Correct |
7 ms |
5484 KB |
Output is correct |
23 |
Correct |
7 ms |
5484 KB |
Output is correct |
24 |
Correct |
6 ms |
5484 KB |
Output is correct |
25 |
Correct |
6 ms |
5484 KB |
Output is correct |
26 |
Correct |
7 ms |
5484 KB |
Output is correct |
27 |
Correct |
6 ms |
5484 KB |
Output is correct |
28 |
Correct |
28 ms |
5500 KB |
Output is correct |
29 |
Correct |
25 ms |
5500 KB |
Output is correct |
30 |
Correct |
26 ms |
5628 KB |
Output is correct |
31 |
Correct |
26 ms |
5664 KB |
Output is correct |
32 |
Correct |
26 ms |
5700 KB |
Output is correct |
33 |
Correct |
26 ms |
5732 KB |
Output is correct |
34 |
Correct |
27 ms |
5832 KB |
Output is correct |
35 |
Correct |
26 ms |
5832 KB |
Output is correct |
36 |
Correct |
28 ms |
5836 KB |
Output is correct |
37 |
Correct |
20 ms |
5868 KB |
Output is correct |
38 |
Correct |
20 ms |
5904 KB |
Output is correct |
39 |
Correct |
20 ms |
5940 KB |
Output is correct |
40 |
Correct |
2204 ms |
19320 KB |
Output is correct |
41 |
Correct |
2112 ms |
19400 KB |
Output is correct |
42 |
Correct |
2151 ms |
19400 KB |
Output is correct |
43 |
Correct |
1928 ms |
19400 KB |
Output is correct |
44 |
Correct |
2029 ms |
19516 KB |
Output is correct |
45 |
Correct |
1867 ms |
19516 KB |
Output is correct |
46 |
Correct |
1902 ms |
19516 KB |
Output is correct |
47 |
Correct |
1476 ms |
19516 KB |
Output is correct |
48 |
Correct |
1716 ms |
19516 KB |
Output is correct |
49 |
Correct |
968 ms |
19516 KB |
Output is correct |
50 |
Correct |
1194 ms |
19516 KB |
Output is correct |
51 |
Correct |
988 ms |
19516 KB |
Output is correct |
52 |
Correct |
2787 ms |
19516 KB |
Output is correct |
53 |
Correct |
2853 ms |
21536 KB |
Output is correct |
54 |
Correct |
2688 ms |
23852 KB |
Output is correct |
55 |
Correct |
2508 ms |
26220 KB |
Output is correct |
56 |
Correct |
2388 ms |
28256 KB |
Output is correct |
57 |
Correct |
2096 ms |
29968 KB |
Output is correct |
58 |
Correct |
2058 ms |
32024 KB |
Output is correct |
59 |
Correct |
1358 ms |
32024 KB |
Output is correct |