#include <bits/stdc++.h>
using ll = long long;
#define int ll
using namespace std;
#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;
const ll N = 2000005;
const ll inf = 1e18;
int n, m, w[N], e[N], vis[N], nxt[N];
vi v;
void solve(){
cin >> n >> m;
foru(i, 1, n){
cin >> w[i] >> e[i];
v.push_back(w[i]);
v.push_back(e[i]);
}
sort(v.begin(), v.end());
foru(i, 0, (n << 1) - 1){
nxt[i] = i + 1;
}
foru(i, 1, n){
w[i] = lower_bound(v.begin(), v.end(), w[i]) - v.begin() + 1;
e[i] = lower_bound(v.begin(), v.end(), e[i]) - v.begin() + 1;
nxt[w[i] - 1] = e[i];
nxt[e[i] - 1] = w[i];
}
nxt[n << 1] = 0;
v.clear();
int res;
foru(i, 0, n << 1){
if(vis[i]) continue;
int cnt = 0;
for(int j = i; !vis[j]; j = nxt[j]){
vis[j] = 1;
cnt++;
}
if(!i) res = cnt;
else v.push_back(cnt);
}
sort(v.begin(), v.end()); res--;
while(m){
if(!sz(v)) break;
else{
res += v.back() + 2;
v.pop_back();
}
m--;
}
res += (m << 1) - (m & 1);
cout << res;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t = 1;
while(t--){
solve();
}
}
Compilation message
teleporters.cpp: In function 'void solve()':
teleporters.cpp:53:31: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
53 | sort(v.begin(), v.end()); res--;
| ~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
616 KB |
Output is correct |
2 |
Correct |
5 ms |
1240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
596 KB |
Output is correct |
2 |
Correct |
7 ms |
1300 KB |
Output is correct |
3 |
Correct |
15 ms |
2628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
1528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
8284 KB |
Output is correct |
2 |
Correct |
223 ms |
19180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
13624 KB |
Output is correct |
2 |
Correct |
348 ms |
34904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
485 ms |
39496 KB |
Output is correct |
2 |
Correct |
642 ms |
58352 KB |
Output is correct |
3 |
Correct |
638 ms |
63736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
828 ms |
55424 KB |
Output is correct |
2 |
Correct |
857 ms |
65536 KB |
Output is correct |
3 |
Correct |
791 ms |
65536 KB |
Output is correct |
4 |
Correct |
824 ms |
65536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
920 ms |
65536 KB |
Output is correct |
2 |
Correct |
884 ms |
65536 KB |
Output is correct |
3 |
Correct |
417 ms |
65536 KB |
Output is correct |
4 |
Correct |
852 ms |
65536 KB |
Output is correct |