# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
825537 | 2023-08-15T02:20:35 Z | Trunkty | Teleporters (IOI08_teleporters) | C++14 | 350 ms | 50736 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll int n,m; int pos[2000005],nex[2000005]; bool check[2000005]; vector<int> v; int cnt,ans; void dfs(int x){ if(check[x]){ return; } check[x] = true; cnt++; dfs(nex[x]); } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i=1;i<=n;i++){ int a,b; cin >> a >> b; pos[a] = i; pos[b] = i+1e6; } int bef=0; for(int i=1;i<=2e6;i++){ if(pos[i]){ nex[bef] = pos[i]; bef = pos[i]; } } for(int i=1;i<=n;i++){ swap(nex[i],nex[i+1000000]); } dfs(0); ans = cnt-1LL; for(int i=1;i<=n;i++){ if(!check[i]){ cnt = 0; dfs(i); v.push_back(cnt); } if(!check[i+1000000]){ cnt = 0; dfs(i+1000000); v.push_back(cnt); } } sort(v.begin(),v.end(),greater<int>()); if(v.size()>=m){ for(int i=0;i<=m-1;i++){ ans += v[i]; } ans += 2LL*m; } else{ for(int i=0;i<v.size();i++){ ans += v[i]; } ans += 2LL*(v.size()); ans += ((m-v.size())/2LL)*4LL; ans += (m-v.size())%2LL; } cout << ans << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 596 KB | Output is correct |
2 | Correct | 5 ms | 980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 620 KB | Output is correct |
2 | Correct | 5 ms | 1620 KB | Output is correct |
3 | Correct | 8 ms | 1620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 7104 KB | Output is correct |
2 | Correct | 94 ms | 19624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 14844 KB | Output is correct |
2 | Correct | 120 ms | 24928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 177 ms | 31192 KB | Output is correct |
2 | Correct | 190 ms | 33348 KB | Output is correct |
3 | Correct | 180 ms | 35672 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 319 ms | 35664 KB | Output is correct |
2 | Correct | 285 ms | 50736 KB | Output is correct |
3 | Correct | 350 ms | 47716 KB | Output is correct |
4 | Correct | 320 ms | 48140 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 283 ms | 41816 KB | Output is correct |
2 | Correct | 290 ms | 41948 KB | Output is correct |
3 | Correct | 155 ms | 41464 KB | Output is correct |
4 | Correct | 236 ms | 41544 KB | Output is correct |