# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
583275 | 2022-06-25T07:36:20 Z | M_W | Teleporters (IOI08_teleporters) | C++17 | 1000 ms | 49312 KB |
#include <bits/stdc++.h> #define ii pair<int, int> using namespace std; int pa[2000002], cnt[2000002], pos[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++) pos[v[i].first] = i; 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]; int getpos = pos[find] + 1; if(getpos == v.size() || vis[getpos]) break; unset(getpos, cur); cur = getpos; } } 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 * 4) + (M % 2); printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 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 | 0 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 416 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 | Incorrect | 0 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 | 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 | 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 | Incorrect | 2 ms | 596 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 596 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 1104 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 1360 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 74 ms | 7512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 165 ms | 13968 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 616 ms | 33776 KB | Output is correct |
2 | Incorrect | 735 ms | 39040 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 885 ms | 44316 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1014 ms | 49312 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |