# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
229552 | 2020-05-05T04:15:07 Z | FieryPhoenix | Teleporters (IOI08_teleporters) | C++11 | 458 ms | 47384 KB |
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 int N,M; int L[1000001],R[1000001]; int adj[2000005]; int tele[2000005]; int label[2000005]; bool vis[2000005]; int ans=0; int cycleSize; vector<int>cyc; void dfs(int node, int from){ vis[node]=true; if (!vis[adj[node]]){ cycleSize++; if (from==0) ans++; dfs(adj[node],from); } } int main() { //ios_base::sync_with_stdio(0);cin.tie(0); //freopen (".in","r",stdin); //freopen (".out","w",stdout); scanf("%d%d",&N,&M); for (int i=1;i<=N;i++){ scanf("%d%d",&L[i],&R[i]); tele[L[i]]=i; tele[R[i]]=i; } int cnt=0; for (int i=1;i<=2000000;i++){ if (tele[i]!=0){ cnt++; label[i]=cnt; } } for (int i=1;i<=2000000;i++){ if (tele[i]!=0){ if (L[tele[i]]==i) adj[label[i]-1]=label[R[tele[i]]]; else adj[label[i]-1]=label[L[tele[i]]]; } } dfs(0,0); for (int i=1;i<=N*2;i++) if (!vis[i]){ cycleSize=0; dfs(i,i); cyc.push_back(cycleSize+1); } sort(cyc.begin(),cyc.end()); reverse(cyc.begin(),cyc.end()); /* cout<<ans<<endl; cout<<"CYCLES: "; for (int x:cyc) cout<<x<<' '; cout<<endl; */ for (int i=0;i<(int)cyc.size();i++){ if (M>0){ ans+=cyc[i]+2; M--; } } while (M>=2){ M-=2; ans+=4; } if (M==1) ans++; cout<<ans<<endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 436 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 512 KB | Output is correct |
2 | Correct | 17 ms | 1160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 640 KB | Output is correct |
2 | Correct | 14 ms | 1536 KB | Output is correct |
3 | Correct | 18 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 1024 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 6904 KB | Output is correct |
2 | Correct | 150 ms | 19188 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 14324 KB | Output is correct |
2 | Correct | 223 ms | 24668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 287 ms | 29292 KB | Output is correct |
2 | Correct | 348 ms | 31596 KB | Output is correct |
3 | Correct | 351 ms | 43624 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 406 ms | 33644 KB | Output is correct |
2 | Correct | 439 ms | 34924 KB | Output is correct |
3 | Correct | 442 ms | 47384 KB | Output is correct |
4 | Correct | 418 ms | 47352 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 458 ms | 37968 KB | Output is correct |
2 | Correct | 455 ms | 37872 KB | Output is correct |
3 | Correct | 301 ms | 37604 KB | Output is correct |
4 | Correct | 429 ms | 37912 KB | Output is correct |