# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
58258 | memikakizaki | Teleporters (IOI08_teleporters) | C++14 | 1085 ms | 39276 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = 1e6+1, INF = 1e9;
int n, m, lf[N], rg[N], nxt[N << 1];
vector<int> vals, cycles;
bitset<N> mark;
long ans;
int main() {
scanf("%d %d", &n, &m);
vals.reserve(2*n+1);
for(int i = 0; i < n; i++) {
scanf("%d %d", &lf[i], &rg[i]);
vals.push_back(lf[i]);
vals.push_back(rg[i]);
}
vals.push_back(INF);
stable_sort(vals.begin(), vals.end());
for(int i = 0; i < n; i++) {
lf[i] = lower_bound(vals.begin(), vals.end(), lf[i]) - vals.begin();
rg[i] = lower_bound(vals.begin(), vals.end(), rg[i]) - vals.begin();
nxt[lf[i]] = rg[i]+1;
nxt[rg[i]] = lf[i]+1;
}
nxt[vals.size()-1] = INF;
for(int i = 0; i < vals.size(); i++) if(!mark[i]) {
int curr = i, sz = 0;
bool cycle = false;
while(curr != INF) {
if(mark[curr]) {
cycle = true;
break;
}
++sz;
mark[curr] = true;
curr = nxt[curr];
}
if(cycle) cycles.push_back(sz);
else ans = sz-1;
}
sort(cycles.begin(), cycles.end(), greater<int>());
for(int i = 0; i < min((int) cycles.size(), m); i++) ans += cycles[i] + 2;
if(m > cycles.size()) {
m -= cycles.size();
ans += (m - (m & 1)) << 1 + (m & 1);
}
printf("%lld", ans);
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |