#include <bits/stdc++.h>
#define N 2000005
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, par[N], ok[N], ans;
vector<int> val;
int bit[N];
void updb(int x, int v)
{
for(int i = x; i < N; i += (i&-i)) bit[i] += v;
}
int queryb(int x)
{
int sum = 0;
for(int i = x; i > 0; i -= (i&-i)) sum += bit[i];
return sum;
}
int prox(int x)
{
int ini = 0, fim = val.size() - 1, mid, best;
while(ini <= fim)
{
mid = (ini + fim)/2;
if(val[mid] > x) best = mid, fim = mid - 1;
else ini = mid + 1;
}
return val[best];
}
int custo = 0;
vector<int> upd;
void dfs(int x, int flag)
{
// cout<<"DFS "<<x<<"\n";
if(x == N) return;
upd.push_back(x);
int p = prox(x);
if(!flag)
{
if(par[x])
{
if(ok[par[x]]) return;
custo ++;
dfs(par[x], 1);
}
else if(!ok[p]) dfs(p, 0);
}
else if(!ok[p]) dfs(p, 0);
}
pii v[N];
int main()
{
//ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 1, x, y; i <= n; i++)
{
cin>>x>>y;
val.push_back(x);
val.push_back(y);
par[x] = y, par[y] = x;
v[i] = {min(x, y), max(x, y)};
}
val.push_back(N);
sort(val.begin(), val.end());
priority_queue<int> heap;
custo = 0;
dfs(0, 0);
ans = custo;
for(auto x: upd) ok[x] = 1;
for(int i = 1; i <= n; i++)
{
int q = upper_bound(val.begin(), val.end(), v[i].s - 1) - lower_bound(val.begin(), val.end(), v[i].f + 1);
if(q <= 0)
{
if(ok[v[i].f] or ok[v[i].s]) heap.push(1);
else heap.push(2);
}
}
for(int i = 1; i < N - 4; i++)
{
if(ok[i]) continue;
upd.clear();
custo = 0;
//cout<<"SOLVE "<<i<<"\n";
dfs(i, 0);
//if(i == N - 5) cout<<"SOLVE "<<i<<"\n";
if(custo > 1) heap.push(2*custo);//, cout<<"SECRETO "<<custo<<"\n";
for(auto x: upd) ok[x] = 1;
}
while(!heap.empty() and m > 0)
{
m --;
ans += 2+ heap.top();
heap.pop();
}
ans += 2*m;
cout<<ans<<"\n";
}
Compilation message
teleporters.cpp: In function 'int prox(int)':
teleporters.cpp:41:20: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
return val[best];
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
8184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
49 ms |
8304 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
8352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
49 ms |
8356 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
53 ms |
8420 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
66 ms |
8476 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
109 ms |
8492 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
67 ms |
8552 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
64 ms |
8600 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
81 ms |
8600 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
77 ms |
8600 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
95 ms |
8760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
93 ms |
8904 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
113 ms |
9340 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
127 ms |
9756 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
341 ms |
15724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
521 ms |
23456 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1066 ms |
39620 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1068 ms |
49352 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1079 ms |
65868 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |