# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
80148 | 2018-10-19T07:14:55 Z | Sherazin | Teleporters (IOI08_teleporters) | C++14 | 1000 ms | 66560 KB |
#include <bits/stdc++.h> #define pii pair<int, int> #define x first #define y second using namespace std; const int N = 2e6+5; int n, m; int chk[N], sz[N], comp; vector<int> pos; map<int, int> mp; int get(int x) { return lower_bound(pos.begin(), pos.end(), x) - pos.begin(); } int main() { scanf("%d %d", &n, &m); for(int i = 1, a, b; i <= n; i++) { scanf("%d %d", &a, &b); pos.emplace_back(a), pos.emplace_back(b); mp[a] = b, mp[b] = a; } pos.emplace_back(1e9); sort(pos.begin(), pos.end()); for(int i = 0; i < 2*n; i++) if(!chk[i]) { chk[i] = ++comp; queue<int> Q; Q.emplace(i); while(!Q.empty()) { int u = Q.front(); Q.pop(); ++sz[comp]; int v = get(mp[pos[u]]) + 1; if(chk[v] || v == 2*n) continue; chk[v] = comp; Q.emplace(v); } } int ans = sz[1]; priority_queue<int> Q; for(int i = 2; i <= comp; i++) Q.emplace(sz[i]); while(!Q.empty() && m) { int z = Q.top(); Q.pop(); ans += z + 2, --m; } ans += 2*(m - (m & 1)) + (m & 1); printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 612 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 632 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 636 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 640 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 644 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 760 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1036 KB | Output is correct |
2 | Correct | 18 ms | 1960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 1960 KB | Output is correct |
2 | Correct | 21 ms | 2484 KB | Output is correct |
3 | Correct | 50 ms | 4708 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 4708 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 4708 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 392 ms | 17880 KB | Output is correct |
2 | Execution timed out | 1040 ms | 40780 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 764 ms | 40780 KB | Output is correct |
2 | Execution timed out | 1075 ms | 62304 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1083 ms | 66560 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1080 ms | 66560 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1068 ms | 66560 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |