이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
cin >> n >> m;
vector<int> tp(2e6 + 1);
vector<pair<int, int>> vpii;
{
vector<int> vi;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
vi.push_back(a), vi.push_back(b);
tp[a] = b, tp[b] = a;
}
sort(vi.begin(), vi.end());
vpii.emplace_back(0, vi[0]);
for (int i = 0; i < vi.size() - 1; i++) {
vpii.emplace_back(vi[i], vi[i + 1]);
}
vpii.emplace_back(vi.back(), 3e6);
}
// for (auto a : vpii) cout << a.first << " " << a.second << "\n";
vector<bool> vb;
vb.resize(vpii.size());
vector<int> cyc;
int special;
for (int i = 0; i < vb.size(); i++)
if (!vb[i]) {
// cout << "I = " << i << '\n';
int cy = 0;
function<void(int)> dfs;
dfs = [&](int cur) {
// cout << cur << "\n";
if (vb[cur]) {
cyc.push_back(cy);
return;
}
vb[cur] = 1;
cy++;
if (vpii[cur].second == 3e6) {
special = cy - 1;
return;
}
dfs(lower_bound(vpii.begin(), vpii.end(),
make_pair(tp[vpii[cur].second], -1)) -
vpii.begin());
};
dfs(i);
}
// for (auto a : cyc) cout << a << ' ';
// cout << "\n";
sort(cyc.begin(), cyc.end(), greater<int>());
if (m >= cyc.size()) {
while(1){}
// cout << (n + m) * 2 << "\n";
// return 0;
cout << special + accumulate(cyc.begin(), cyc.end(), 0) + m * 2 << "\n";
} else
cout << special + accumulate(cyc.begin(), cyc.begin() + m, 0) + 2 * m
<< "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
teleporters.cpp: In function 'int main()':
teleporters.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 0; i < vi.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~
teleporters.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < vb.size(); i++)
| ~~^~~~~~~~~~~
teleporters.cpp:56:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if (m >= cyc.size()) {
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |