# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
583268 | 2022-06-25T07:29:22 Z | M_W | Teleporters (IOI08_teleporters) | C++17 | 1000 ms | 53164 KB |
#include <bits/stdc++.h> #define ii pair<int, int> using namespace std; int pa[2000002], cnt[2000002]; // i * 2 = st, i * 2 + 1 = ed; int in[1000001], out[1000001]; bool vis[2000002]; map<int, int> mp; int findpa(int a){ return pa[a] == a ? a : pa[a] = findpa(pa[a]); } void unset(int u, int v){ cnt[findpa(v)] += cnt[findpa(u)]; pa[findpa(u)] = findpa(v); } int main(){ int N, M; vector<ii> v; scanf("%d %d", &N, &M); for(int i = 1; i <= N; i++){ pa[i * 2] = i * 2; pa[i * 2 + 1] = i * 2 + 1; cnt[i * 2] = cnt[i * 2 + 1] = 1; scanf("%d %d", &in[i], &out[i]); v.push_back({in[i], i * 2}); v.push_back({out[i], i * 2 + 1}); } sort(v.begin(), v.end()); for(int i = 0; i < v.size(); i++){ if(vis[v[i].second]) continue; int cur = v[i].second; while(true){ vis[cur] = true; int find = cur & 1 ? in[cur >> 1] : out[cur >> 1]; auto it = upper_bound(v.begin(), v.end(), make_pair(find, INT_MAX)); if(it == v.end() || vis[(*it).second]) break; unset((*it).second, cur); cur = (*it).second; } } int ans = cnt[v[0].second]; priority_queue<int> pq; for(int i = 2; i <= (N * 2) + 1; i++){ if(pa[i] != i || i == v[0].second) continue; pq.push(cnt[i]); } while(!pq.empty() && M > 0){ ans += pq.top() + 2; pq.pop(); M--; } ans += (M * 2) + (M % 2); printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 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 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 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 | 292 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 | 468 KB | Output is correct |
2 | Correct | 7 ms | 860 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 468 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 1360 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 5880 KB | Output is correct |
2 | Correct | 294 ms | 18804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 186 ms | 9996 KB | Output is correct |
2 | Incorrect | 528 ms | 19748 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 574 ms | 29608 KB | Output is correct |
2 | Correct | 744 ms | 35204 KB | Output is correct |
3 | Correct | 693 ms | 53164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 985 ms | 39880 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1018 ms | 47944 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |