#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2e5 + 5;
priority_queue<int> heap;
int start[Nmax], finish[Nmax], add[Nmax], dp[Nmax];
vector<int> v[Nmax];
int n, m, i;
vector< pair<int,int> > edges;
int mod(int x)
{
if(x <= 0) return x+n;
if(x>n) return x-n;
return x;
}
bool check_center(int where, int L)
{
int i, need = 0, nr;
for(i=1; i<=n; ++i) v[i].clear();
for(auto e : edges)
{
int x, y;
x = mod(e.first - where + 1);
y = mod(e.second - where + 1);
if(x > y) swap(x, y);
v[x].push_back(y);
}
while(heap.size()) heap.pop();
for(i=1; i<=n; ++i) finish[i] = 0;
for(i=1; i<=n; ++i)
{
start[i] = v[i].size(); add[i] = 0;
for(auto it : v[i]) finish[it] ++;
}
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 && need <= L)
{
assert(heap.size());
dp[i] -= 2;
nr = heap.top();
heap.pop();
add[nr] += 2;
++need;
}
if(need > L) return 0;
}
return (need <= L);
}
bool check(int L)
{
int i;
for(i=1; i<=n; ++i)
if(check_center(i, L)) return 1;
return 0;
}
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});
}
for(i=1; i<=n; ++i) sort(v[i].begin(), v[i].end());
int st = 0, dr = m, mid;
while(st <= dr)
{
mid = (st+dr) / 2;
if(check(mid)) dr = mid - 1;
else st = mid + 1;
}
cout << st << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5116 KB |
Output is correct |
3 |
Correct |
6 ms |
5164 KB |
Output is correct |
4 |
Correct |
6 ms |
5232 KB |
Output is correct |
5 |
Correct |
6 ms |
5260 KB |
Output is correct |
6 |
Correct |
6 ms |
5448 KB |
Output is correct |
7 |
Correct |
6 ms |
5488 KB |
Output is correct |
8 |
Correct |
6 ms |
5488 KB |
Output is correct |
9 |
Correct |
6 ms |
5488 KB |
Output is correct |
10 |
Correct |
6 ms |
5488 KB |
Output is correct |
11 |
Correct |
6 ms |
5488 KB |
Output is correct |
12 |
Correct |
6 ms |
5488 KB |
Output is correct |
13 |
Correct |
6 ms |
5564 KB |
Output is correct |
14 |
Correct |
6 ms |
5564 KB |
Output is correct |
15 |
Correct |
6 ms |
5612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5116 KB |
Output is correct |
3 |
Correct |
6 ms |
5164 KB |
Output is correct |
4 |
Correct |
6 ms |
5232 KB |
Output is correct |
5 |
Correct |
6 ms |
5260 KB |
Output is correct |
6 |
Correct |
6 ms |
5448 KB |
Output is correct |
7 |
Correct |
6 ms |
5488 KB |
Output is correct |
8 |
Correct |
6 ms |
5488 KB |
Output is correct |
9 |
Correct |
6 ms |
5488 KB |
Output is correct |
10 |
Correct |
6 ms |
5488 KB |
Output is correct |
11 |
Correct |
6 ms |
5488 KB |
Output is correct |
12 |
Correct |
6 ms |
5488 KB |
Output is correct |
13 |
Correct |
6 ms |
5564 KB |
Output is correct |
14 |
Correct |
6 ms |
5564 KB |
Output is correct |
15 |
Correct |
6 ms |
5612 KB |
Output is correct |
16 |
Correct |
36 ms |
5788 KB |
Output is correct |
17 |
Correct |
35 ms |
5788 KB |
Output is correct |
18 |
Correct |
29 ms |
5788 KB |
Output is correct |
19 |
Correct |
41 ms |
5788 KB |
Output is correct |
20 |
Correct |
29 ms |
5788 KB |
Output is correct |
21 |
Correct |
36 ms |
5788 KB |
Output is correct |
22 |
Correct |
35 ms |
5788 KB |
Output is correct |
23 |
Correct |
23 ms |
5796 KB |
Output is correct |
24 |
Correct |
35 ms |
5800 KB |
Output is correct |
25 |
Correct |
45 ms |
5932 KB |
Output is correct |
26 |
Correct |
27 ms |
5932 KB |
Output is correct |
27 |
Correct |
28 ms |
5932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5116 KB |
Output is correct |
3 |
Correct |
6 ms |
5164 KB |
Output is correct |
4 |
Correct |
6 ms |
5232 KB |
Output is correct |
5 |
Correct |
6 ms |
5260 KB |
Output is correct |
6 |
Correct |
6 ms |
5448 KB |
Output is correct |
7 |
Correct |
6 ms |
5488 KB |
Output is correct |
8 |
Correct |
6 ms |
5488 KB |
Output is correct |
9 |
Correct |
6 ms |
5488 KB |
Output is correct |
10 |
Correct |
6 ms |
5488 KB |
Output is correct |
11 |
Correct |
6 ms |
5488 KB |
Output is correct |
12 |
Correct |
6 ms |
5488 KB |
Output is correct |
13 |
Correct |
6 ms |
5564 KB |
Output is correct |
14 |
Correct |
6 ms |
5564 KB |
Output is correct |
15 |
Correct |
6 ms |
5612 KB |
Output is correct |
16 |
Correct |
36 ms |
5788 KB |
Output is correct |
17 |
Correct |
35 ms |
5788 KB |
Output is correct |
18 |
Correct |
29 ms |
5788 KB |
Output is correct |
19 |
Correct |
41 ms |
5788 KB |
Output is correct |
20 |
Correct |
29 ms |
5788 KB |
Output is correct |
21 |
Correct |
36 ms |
5788 KB |
Output is correct |
22 |
Correct |
35 ms |
5788 KB |
Output is correct |
23 |
Correct |
23 ms |
5796 KB |
Output is correct |
24 |
Correct |
35 ms |
5800 KB |
Output is correct |
25 |
Correct |
45 ms |
5932 KB |
Output is correct |
26 |
Correct |
27 ms |
5932 KB |
Output is correct |
27 |
Correct |
28 ms |
5932 KB |
Output is correct |
28 |
Correct |
2486 ms |
6124 KB |
Output is correct |
29 |
Execution timed out |
6037 ms |
6168 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5116 KB |
Output is correct |
3 |
Correct |
6 ms |
5164 KB |
Output is correct |
4 |
Correct |
6 ms |
5232 KB |
Output is correct |
5 |
Correct |
6 ms |
5260 KB |
Output is correct |
6 |
Correct |
6 ms |
5448 KB |
Output is correct |
7 |
Correct |
6 ms |
5488 KB |
Output is correct |
8 |
Correct |
6 ms |
5488 KB |
Output is correct |
9 |
Correct |
6 ms |
5488 KB |
Output is correct |
10 |
Correct |
6 ms |
5488 KB |
Output is correct |
11 |
Correct |
6 ms |
5488 KB |
Output is correct |
12 |
Correct |
6 ms |
5488 KB |
Output is correct |
13 |
Correct |
6 ms |
5564 KB |
Output is correct |
14 |
Correct |
6 ms |
5564 KB |
Output is correct |
15 |
Correct |
6 ms |
5612 KB |
Output is correct |
16 |
Correct |
36 ms |
5788 KB |
Output is correct |
17 |
Correct |
35 ms |
5788 KB |
Output is correct |
18 |
Correct |
29 ms |
5788 KB |
Output is correct |
19 |
Correct |
41 ms |
5788 KB |
Output is correct |
20 |
Correct |
29 ms |
5788 KB |
Output is correct |
21 |
Correct |
36 ms |
5788 KB |
Output is correct |
22 |
Correct |
35 ms |
5788 KB |
Output is correct |
23 |
Correct |
23 ms |
5796 KB |
Output is correct |
24 |
Correct |
35 ms |
5800 KB |
Output is correct |
25 |
Correct |
45 ms |
5932 KB |
Output is correct |
26 |
Correct |
27 ms |
5932 KB |
Output is correct |
27 |
Correct |
28 ms |
5932 KB |
Output is correct |
28 |
Correct |
2486 ms |
6124 KB |
Output is correct |
29 |
Execution timed out |
6037 ms |
6168 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5116 KB |
Output is correct |
3 |
Correct |
6 ms |
5164 KB |
Output is correct |
4 |
Correct |
6 ms |
5232 KB |
Output is correct |
5 |
Correct |
6 ms |
5260 KB |
Output is correct |
6 |
Correct |
6 ms |
5448 KB |
Output is correct |
7 |
Correct |
6 ms |
5488 KB |
Output is correct |
8 |
Correct |
6 ms |
5488 KB |
Output is correct |
9 |
Correct |
6 ms |
5488 KB |
Output is correct |
10 |
Correct |
6 ms |
5488 KB |
Output is correct |
11 |
Correct |
6 ms |
5488 KB |
Output is correct |
12 |
Correct |
6 ms |
5488 KB |
Output is correct |
13 |
Correct |
6 ms |
5564 KB |
Output is correct |
14 |
Correct |
6 ms |
5564 KB |
Output is correct |
15 |
Correct |
6 ms |
5612 KB |
Output is correct |
16 |
Correct |
36 ms |
5788 KB |
Output is correct |
17 |
Correct |
35 ms |
5788 KB |
Output is correct |
18 |
Correct |
29 ms |
5788 KB |
Output is correct |
19 |
Correct |
41 ms |
5788 KB |
Output is correct |
20 |
Correct |
29 ms |
5788 KB |
Output is correct |
21 |
Correct |
36 ms |
5788 KB |
Output is correct |
22 |
Correct |
35 ms |
5788 KB |
Output is correct |
23 |
Correct |
23 ms |
5796 KB |
Output is correct |
24 |
Correct |
35 ms |
5800 KB |
Output is correct |
25 |
Correct |
45 ms |
5932 KB |
Output is correct |
26 |
Correct |
27 ms |
5932 KB |
Output is correct |
27 |
Correct |
28 ms |
5932 KB |
Output is correct |
28 |
Correct |
2486 ms |
6124 KB |
Output is correct |
29 |
Execution timed out |
6037 ms |
6168 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |