# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
583277 | 2022-06-25T07:38:25 Z | M_W | Teleporters (IOI08_teleporters) | C++17 | 856 ms | 57232 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; ii newpos = v[getpos]; if(getpos == v.size() || vis[newpos.second]) break; unset(newpos.second, cur); cur = newpos.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 * 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 | 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 | 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 | 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 | 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 | 5 ms | 1104 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 596 KB | Output is correct |
2 | Correct | 6 ms | 1300 KB | Output is correct |
3 | Correct | 14 ms | 1996 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1104 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 | 78 ms | 7804 KB | Output is correct |
2 | Correct | 251 ms | 20000 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 150 ms | 14748 KB | Output is correct |
2 | Correct | 388 ms | 27440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 513 ms | 37460 KB | Output is correct |
2 | Correct | 611 ms | 42872 KB | Output is correct |
3 | Correct | 576 ms | 47752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 801 ms | 47708 KB | Output is correct |
2 | Correct | 794 ms | 51184 KB | Output is correct |
3 | Correct | 713 ms | 48964 KB | Output is correct |
4 | Correct | 721 ms | 49312 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 853 ms | 55744 KB | Output is correct |
2 | Correct | 856 ms | 56100 KB | Output is correct |
3 | Correct | 430 ms | 57232 KB | Output is correct |
4 | Correct | 683 ms | 57204 KB | Output is correct |